{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 机器学习练习-KNN算法\n",
    "代码更新地址：https://github.com/fengdu78/WZU-machine-learning-course\n",
    "\n",
    "代码修改并注释：黄海广，haiguang2000@wzu.edu.cn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1．$k$近邻法是基本且简单的分类与回归方法。$k$近邻法的基本做法是：对给定的训练实例点和输入实例点，首先确定输入实例点的$k$个最近邻训练实例点，然后利用这$k$个训练实例点的类的多数来预测输入实例点的类。\n",
    "\n",
    "2．$k$近邻模型对应于基于训练数据集对特征空间的一个划分。$k$近邻法中，当训练集、距离度量、$k$值及分类决策规则确定后，其结果唯一确定。\n",
    "\n",
    "3．$k$近邻法三要素：距离度量、$k$值的选择和分类决策规则。常用的距离度量是欧氏距离及更一般的**pL**距离。$k$值小时，$k$近邻模型更复杂；$k$值大时，$k$近邻模型更简单。$k$值的选择反映了对近似误差与估计误差之间的权衡，通常由交叉验证选择最优的$k$。\n",
    "\n",
    "常用的分类决策规则是多数表决，对应于经验风险最小化。\n",
    "\n",
    "4．$k$近邻法的实现需要考虑如何快速搜索k个最近邻点。**kd**树是一种便于对k维空间中的数据进行快速检索的数据结构。kd树是二叉树，表示对$k$维空间的一个划分，其每个结点对应于$k$维空间划分中的一个超矩形区域。利用**kd**树可以省去对大部分数据点的搜索， 从而减少搜索的计算量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.距离度量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在机器学习算法中，我们经常需要计算样本之间的相似度，通常的做法是计算样本之间的距离。\n",
    "\n",
    "设$x$和$y$为两个向量，求它们之间的距离。\n",
    "\n",
    "这里用Numpy实现，设和为`ndarray <numpy.ndarray>`，它们的shape都是`(N,)`\n",
    "\n",
    "$d$为所求的距离，是个浮点数（`float`）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np  #注意：运行代码时候需要导入NumPy库。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 欧氏距离(Euclidean distance)\n",
    "\n",
    "欧几里得度量(euclidean metric)(也称欧氏距离)是一个通常采用的距离定义，指在$m$维空间中两个点之间的真实距离，或者向量的自然长度(即该点到原点的距离)。在二维和三维空间中的欧氏距离就是两点之间的实际距离。\n",
    "\n",
    "距离公式：\n",
    "\n",
    "$$\n",
    "d\\left( x,y \\right) = \\sqrt{\\sum_{i}^{}(x_{i} - y_{i})^{2}}\n",
    "$$\n",
    "\n",
    "![img](images/16333182861.jpg)\n",
    "\n",
    "\n",
    "\n",
    "代码实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def euclidean(x, y):\n",
    "\n",
    "    return np.sqrt(np.sum((x - y)**2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 曼哈顿距离(Manhattan distance)\n",
    "\n",
    "想象你在城市道路里，要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源，曼哈顿距离也称为城市街区距离(City Block distance)。\n",
    "\n",
    "距离公式：\n",
    "\n",
    "$$\n",
    "d(x,y) = \\sum_{i}^{}|x_{i} - y_{i}|\n",
    "$$\n",
    "\n",
    "![](images/638038949250eedd844a38a93a76f66b.png)\n",
    "\n",
    "\n",
    "\n",
    "代码实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def manhattan(x, y):\n",
    "\n",
    "    return np.sum(np.abs(x - y))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 切比雪夫距离(Chebyshev distance)\n",
    "\n",
    "在数学中，切比雪夫距离(Chebyshev distance)或是L∞度量，是向量空间中的一种度量，二个点之间的距离定义是其各坐标数值差绝对值的最大值。以数学的观点来看，切比雪夫距离是由一致范数(uniform norm)(或称为上确界范数)所衍生的度量，也是超凸度量(injective metric space)的一种。\n",
    "\n",
    "距离公式："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "d\\left( x,y \\right) = \\max_{i}\\left| x_{i} - y_{i} \\right|\n",
    "$$\n",
    "\n",
    "![](images/c7e66b17c54eb109e6474a2d93a877f1.jpg)\n",
    "\n",
    "\n",
    "若将国际象棋棋盘放在二维直角座标系中，格子的边长定义为1，座标的$x$轴及$y$轴和棋盘方格平行，原点恰落在某一格的中心点，则王从一个位置走到其他位置需要的步数恰为二个位置的切比雪夫距离，因此切比雪夫距离也称为棋盘距离。例如位置F6和位置E2的切比雪夫距离为4。任何一个不在棋盘边缘的位置，和周围八个位置的切比雪夫距离都是1。\n",
    "\n",
    "代码实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def chebyshev(x, y):\n",
    "\n",
    "    return np.max(np.abs(x - y))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 闵可夫斯基距离(Minkowski distance)\n",
    "\n",
    "闵氏空间指狭义相对论中由一个时间维和三个空间维组成的时空，为俄裔德国数学家闵可夫斯基(H.Minkowski,1864-1909)最先表述。他的平坦空间(即假设没有重力，曲率为零的空间)的概念以及表示为特殊距离量的几何学是与狭义相对论的要求相一致的。闵可夫斯基空间不同于牛顿力学的平坦空间。$p$取1或2时的闵氏距离是最为常用的，$p= 2$即为欧氏距离，而$p =1$时则为曼哈顿距离。\n",
    "\n",
    "当$p$取无穷时的极限情况下，可以得到切比雪夫距离。\n",
    "\n",
    "距离公式：\n",
    "\n",
    "$$\n",
    "d\\left( x,y \\right) = \\left( \\sum_{i}^{}|x_{i} - y_{i}|^{p} \\right)^{\\frac{1}{p}}\n",
    "$$\n",
    "\n",
    "代码实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minkowski(x, y, p):\n",
    "\n",
    "    return np.sum(np.abs(x - y)**p)**(1 / p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 汉明距离(Hamming distance)\n",
    "\n",
    "汉明距离是使用在数据传输差错控制编码里面的，汉明距离是一个概念，它表示两个(相同长度)字对应位不同的数量，我们以表示两个字,之间的汉明距离。对两个字符串进行异或运算，并统计结果为1的个数，那么这个数就是汉明距离。\n",
    "\n",
    "距离公式：\n",
    "\n",
    "$$\n",
    "d\\left( x,y \\right) = \\frac{1}{N}\\sum_{i}^{}1_{x_{i} \\neq y_{i}}\n",
    "$$\n",
    "\n",
    "![](images/5ef40ff2f81af854180751680fb334fd.jpg)\n",
    "\n",
    "\n",
    "代码实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hamming(x, y):\n",
    "\n",
    "    return np.sum(x != y) / len(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 余弦相似度(Cosine Similarity)\n",
    "\n",
    "余弦相似性通过测量两个向量的夹角的余弦值来度量它们之间的相似性。0度角的余弦值是1，而其他任何角度的余弦值都不大于1；并且其最小值是-1。从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向。两个向量有相同的指向时，余弦相似度的值为1；两个向量夹角为90°时，余弦相似度的值为0；两个向量指向完全相反的方向时，余弦相似度的值为-1。这结果是与向量的长度无关的，仅仅与向量的指向方向相关。余弦相似度通常用于正空间，因此给出的值为0到1之间。\n",
    "\n",
    "![ ](images/61876887fce99b1e847ad72531f3b650.jpg)\n",
    "\n",
    "\n",
    "\n",
    "二维空间为例，上图的$a$和$b$是两个向量，我们要计算它们的夹角θ。余弦定理告诉我们，可以用下面的公式求得：\n",
    "\n",
    "$$\n",
    "\\cos\\theta = \\frac{a^{2} + b^{2} - c^{2}}{2ab}\n",
    "$$\n",
    "\n",
    "假定$a$向量是$\\left\\lbrack x_{1},y_{1}\n",
    "\\right\\rbrack$，$b$向量是$\\left\\lbrack x_{2},y_{2}\n",
    "\\right\\rbrack$，两个向量间的余弦值可以通过使用欧几里得点积公式求出：\n",
    "\n",
    "$$\n",
    "\\cos\\left( \\theta \\right) = \\frac{A \\cdot B}{\\parallel A \\parallel \\parallel B \\parallel} = \\frac{\\sum_{i = 1}^{n}A_{i} \\times B_{i}}{\\sqrt{\\sum_{i = 1}^{n}(A_{i})^{2} \\times \\sqrt{\\sum_{i = 1}^{n}(B_{i})^{2}}}}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\cos\\left( \\theta \\right) = \\frac{A \\cdot B}{\\parallel A \\parallel \\parallel B \\parallel} = \\frac{\\left( x_{1},y_{1} \\right) \\cdot \\left( x_{2},y_{2} \\right)}{\\sqrt{x_{1}^{2} + y_{1}^{2}} \\times \\sqrt{x_{2}^{2} + y_{2}^{2}}} = \\frac{x_{1}x_{2} + y_{1}y_{2}}{\\sqrt{x_{1}^{2} + y_{1}^{2}} \\times \\sqrt{x_{2}^{2} + y_{2}^{2}}}\n",
    "$$\n",
    "\n",
    "如果向量$a$和$b$不是二维而是$n$维，上述余弦的计算法仍然正确。假定$A$和$B$是两个$n$维向量，$A$是$\\left\\lbrack\n",
    "A_{1},A_{2},\\ldots,A_{n} \\right\\rbrack$，$B$是$\\left\\lbrack\n",
    "B_{1},B_{2},\\ldots,B_{n} \\right\\rbrack$，则$A$与$B$的夹角余弦等于：\n",
    "\n",
    "$$\n",
    "\\cos\\left( \\theta \\right) = \\frac{A \\cdot B}{\\parallel A \\parallel \\parallel B \\parallel} = \\frac{\\sum_{i = 1}^{n}A_{i} \\times B_{i}}{\\sqrt{\\sum_{i = 1}^{n}(A_{i})^{2}} \\times \\sqrt{\\sum_{i = 1}^{n}(B_{i})^{2}}}\n",
    "$$\n",
    "\n",
    "![](images/713ca7c3b9047e27166244a0f047ffe7.jpg)\n",
    "\n",
    "代码实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import *\n",
    "\n",
    "def square_rooted(x):\n",
    "\n",
    "    return round(sqrt(sum([a*a for a in x])),3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cosine_similarity(x, y):\n",
    "\n",
    "    numerator = sum(a * b for a, b in zip(x, y))\n",
    "    denominator = square_rooted(x) * square_rooted(y)\n",
    "    return round(numerator / float(denominator), 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.972\n"
     ]
    }
   ],
   "source": [
    "print(cosine_similarity([3, 45, 7, 2], [2, 54, 13, 15]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## KNN算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1．$k$近邻法是基本且简单的分类与回归方法。$k$近邻法的基本做法是：对给定的训练实例点和输入实例点，首先确定输入实例点的$k$个最近邻训练实例点，然后利用这$k$个训练实例点的类的多数来预测输入实例点的类。\n",
    "\n",
    "2．$k$近邻模型对应于基于训练数据集对特征空间的一个划分。$k$近邻法中，当训练集、距离度量、$k$值及分类决策规则确定后，其结果唯一确定。\n",
    "\n",
    "3．$k$近邻法三要素：距离度量、$k$值的选择和分类决策规则。常用的距离度量是欧氏距离。$k$值小时，$k$近邻模型更复杂；$k$值大时，$k$近邻模型更简单。$k$值的选择反映了对近似误差与估计误差之间的权衡，通常由交叉验证选择最优的$k$。\n",
    "\n",
    "常用的分类决策规则是多数表决，对应于经验风险最小化。\n",
    "\n",
    "4．$k$近邻法的实现需要考虑如何快速搜索k个最近邻点。**kd**树是一种便于对k维空间中的数据进行快速检索的数据结构。kd树是二叉树，表示对$k$维空间的一个划分，其每个结点对应于$k$维空间划分中的一个超矩形区域。利用**kd**树可以省去对大部分数据点的搜索， 从而减少搜索的计算量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "python实现，遍历所有数据点，找出$n$个距离最近的点的分类情况，少数服从多数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn.datasets import load_iris\n",
    "from sklearn.model_selection import train_test_split\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "导入鸢尾花数据集"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "iris = load_iris()\n",
    "df = pd.DataFrame(iris.data, columns=iris.feature_names)\n",
    "df['label'] = iris.target\n",
    "df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>sepal length</th>\n",
       "      <th>sepal width</th>\n",
       "      <th>petal length</th>\n",
       "      <th>petal width</th>\n",
       "      <th>label</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>5.1</td>\n",
       "      <td>3.5</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>4.9</td>\n",
       "      <td>3.0</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>4.7</td>\n",
       "      <td>3.2</td>\n",
       "      <td>1.3</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4.6</td>\n",
       "      <td>3.1</td>\n",
       "      <td>1.5</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5.0</td>\n",
       "      <td>3.6</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   sepal length  sepal width  petal length  petal width  label\n",
       "0           5.1          3.5           1.4          0.2      0\n",
       "1           4.9          3.0           1.4          0.2      0\n",
       "2           4.7          3.2           1.3          0.2      0\n",
       "3           4.6          3.1           1.5          0.2      0\n",
       "4           5.0          3.6           1.4          0.2      0"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "选择长和宽的数据进行可视化"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAtgAAAHoCAYAAABzQZg1AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAA2/0lEQVR4nO3df5xed13n/dfH6dSOAolAEJIJpIDmVkq1MFC67AOBsEZqWyp696aKWGFFEK1sId5kt3eo0RV2s/KjolS0a4VC2YhxIF0gQgAXXVqcNJBRagQKNDPhRyg7KYULGIbP/ce5Jpm5OjOZk5xrznWueT0fj+txzflcZ8585pzrat5z+j3fE5mJJEmSpGp8X90NSJIkSf3EgC1JkiRVyIAtSZIkVciALUmSJFXIgC1JkiRVyIAtSZIkVeisuhuIiAFgDJjMzEs6Xns68G7gc+3SnszcudT2HvrQh+amTZuqb1SSJEma48CBA1/NzHWd9doDNvDbwJ3AgxZ5/aOdwXspmzZtYmxsrJLGJEmSpMVExBcWqtc6RCQihoGfBf68zj4kSZKkqtQ9BvsNwO8A31tinYsi4pMR8b6IeNxCK0TEiyNiLCLGjh071o0+JUmSpGWpLWBHxCXAVzLzwBKr3QE8KjN/AvgjYHShlTLzLZk5kpkj69bdbxiMJEmStGLqHIP9VOCyiLgYOAd4UETcnJnPn10hM++d8/V7I+JPIuKhmfnVGvqVJElShaanp5mYmOBb3/pW3a0s6ZxzzmF4eJjBwcFlrV9bwM7M7cB2ODFbyCvnhut2/eHAlzMzI+LJFGfc71nhViVJktQFExMTPPCBD2TTpk1ERN3tLCgzueeee5iYmODcc89d1vf0wiwi80TESwAy8wbgF4CXRsR3gRbwvMzMOvuTJElSNb71rW/1dLgGiAge8pCHUOY6v54I2Jn5EeAj7a9vmFN/E/CmerqSJElSt/VyuJ5Vtse6ZxGRJEmS+ooBW5IkSava+9//fjZv3sxjH/tYXvva157x9npiiIgkSZJ0KqMHJ9m17zBHp1qsXzvEtq2bufyCDWe0zZmZGV72spfxgQ98gOHhYZ70pCdx2WWX8eM//uOnvU3PYEuSJKnnjR6cZPuecSanWiQwOdVi+55xRg9OntF2P/7xj/PYxz6WRz/60Zx99tk873nP493vfvcZbdOALUmSpJ63a99hWtMz82qt6Rl27Tt8RtudnJxk48aNJ5aHh4eZnDyz0G7AliRJUs87OtUqVV+uhWaAPtOZTQzYkiRJ6nnr1w6Vqi/X8PAwR44cObE8MTHB+vXrz2ibBmxJkiT1vG1bNzM0ODCvNjQ4wLatm89ou0960pP49Kc/zec+9zm+853v8M53vpPLLrvsjLbpLCKSpGXpxtX7krRcs/+9qfq/Q2eddRZvetOb2Lp1KzMzM7zwhS/kcY973Jlt84y+W5K0KsxevT97gdHs1fuAIVvSirn8gg1d+W/OxRdfzMUXX1zZ9hwiIkk6pW5dvS9J/ciALUk6pW5dvS9J/ciALUk6pW5dvS9J/ciALUk6pW5dvS9J/ciLHCVJp9Stq/clqR8ZsCVJy9Ktq/clqd84RESSJEmr2gtf+EIe9rCHcd5551WyPQO2JEmSmuHQbnj9eXDd2uL50O5KNnvVVVfx/ve/v5JtgQFbkiRJTXBoN+y9Go4fAbJ43nt1JSH7aU97Gg9+8IPPvMc2A7YkSZJ63/6dMN0x9/50q6j3GAO2JEmSet/xiXL1GhmwJUmS1PvWDJer18iALUmSpN63ZQcMdtw9dnCoqPcYA7YkSZJ63/lXwKXXw5qNQBTPl15f1M/QlVdeyUUXXcThw4cZHh7mxhtvPKPteaMZSZIkNcP5V1QSqDvdcsstlW7PM9iSJElShQzYkiRJUoUM2JIkSapNZtbdwimV7dGALUmSpFqcc8453HPPPT0dsjOTe+65h3POOWfZ3+NFjpIkSarF8PAwExMTHDt2rO5WlnTOOecwPLz8+bYN2JIkSarF4OAg5557bt1tVM4hIpIkSVKFDNiSJElShQzYkiRJUoUM2JIkSVKFDNiSJElShQzYkiRJUoUM2JIkSVKFDNiSJElShQzYkiRJUoUM2JIkSVKFvFW6JNVg9OAku/Yd5uhUi/Vrh9i2dTOXX7Ch7rYkSRUwYEvSChs9OMn2PeO0pmcAmJxqsX3POIAhW5L6gENEJGmF7dp3+ES4ntWanmHXvsM1dSRJqpIBW5JW2NGpVqm6JKlZDNiStMLWrx0qVZckNYsBW5JW2LatmxkaHJhXGxocYNvWzTV1JEmqkhc5StIKm72Q0VlEJKk/GbAlqQaXX7DBQC1JfcohIpIkSVKFDNiSJElShQzYkiRJUoUM2JIkSVKFDNiSJElShQzYkiRJUoUM2JIkSVKFDNiSJElShbzRjKQVM3pw0rsXSpL6ngFb0ooYPTjJ9j3jtKZnAJicarF9zziAIVuS1FccIiJpRezad/hEuJ7Vmp5h177DNXUkSVJ3GLAlrYijU61SdUmSmsqALWlFrF87VKouSVJTGbAlrYhtWzczNDgwrzY0OMC2rZtr6kiSpO7wIkdJK2L2QkZnEZEk9TsDtqQVc/kFGwzUkqS+5xARSZIkqUIGbEmSJKlCBmxJkiSpQgZsSZIkqUIGbEmSJKlCBmxJkiSpQgZsSZIkqUIGbEmSJKlCBmxJkiSpQrXfyTEiBoAxYDIzL+l4LYA3AhcD3wSuysw7Vr5LSVI3jR6cZNe+wxydarF+7RDbtm72rp+SGqv2gA38NnAn8KAFXns28CPtx4XAm9vPkqQ+MXpwku17xmlNzwAwOdVi+55xAEO2pEaqdYhIRAwDPwv8+SKrPAd4axZuA9ZGxCNWrEFJUtft2nf4RLie1ZqeYde+wzV1JElnpu4x2G8Afgf43iKvbwCOzFmeaNfmiYgXR8RYRIwdO3as8iYlSd1zdKpVqi5Jva62gB0RlwBfycwDS622QC3vV8h8S2aOZObIunXrKutRktR969cOlapLUq+r8wz2U4HLIuLzwDuBZ0bEzR3rTAAb5ywPA0dXpj1J0krYtnUzQ4MD82pDgwNs27q5po4k6czUFrAzc3tmDmfmJuB5wIcy8/kdq70HeEEUngIcz8wvrnSvkqTuufyCDbzmuY9nw9ohAtiwdojXPPfxXuAoqbF6YRaReSLiJQCZeQPwXoop+j5DMU3fr9bYmiSpSy6/YIOBWlLf6ImAnZkfAT7S/vqGOfUEXlZPV5IkSVJ5dc8iIkmSJPUVA7YkSZJUIQO2JEmSVCEDtiRJklQhA7YkSZJUIQO2JEmSVCEDtiRJklShnpgHW5J61bWj49xy+xFmMhmI4MoLN/L7lz++7rYkST3MgC1Ji7h2dJybb7v7xPJM5ollQ7YkaTEOEZGkRdxy+5FSdUmSwIAtSYuaySxVlyQJDNiStKiBiFJ1SZLAgC1Ji7rywo2l6pIkgRc5StKiZi9kdBYRSVIZkX02lnBkZCTHxsbqbkOSJEl9LiIOZOZIZ90hIpIkSVKFDNiSJElShQzYkiRJUoUM2JIkSVKFDNiSJElShQzYkiRJUoUM2JIkSVKFDNiSJElShQzYkiRJUoW8VbqkeX7pzz7GP3z2ayeWn/qYB/P2X7uoxo7UK0YPTrJr32GOTrVYv3aIbVs3c/kFG+puS5J6jmewJZ3QGa4B/uGzX+OX/uxjNXWkXjF6cJLte8aZnGqRwORUi+17xhk9OFl3a5LUcwzYkk7oDNenqmv12LXvMK3pmXm11vQMu/YdrqkjSepdBmxJ0ikdnWqVqkvSambAliSd0vq1Q6XqkrSaGbAlnfDUxzy4VF2rx7atmxkaHJhXGxocYNvWzTV1JEm9y4At6YS3/9pF9wvTziIigMsv2MBrnvt4NqwdIoANa4d4zXMf7ywikrSAyMy6e6jUyMhIjo2N1d2GJEmS+lxEHMjMkc66Z7AlSZKkChmwJUmSpAoZsCVJkqQKGbAlSZKkChmwJUmSpAoZsCVJkqQKGbAlSZKkChmwJUmSpAqdVXcDknrL6MFJdu07zNGpFuvXDrFt6+aev1tfN3tu4v6QJNXLgC3phNGDk2zfM05regaAyakW2/eMA/RsqOxmz03cH5Kk+jlERNIJu/YdPhEmZ7WmZ9i173BNHZ1aN3tu4v6QJNXPgC3phKNTrVL1XtDNnpu4PyRJ9TNgSzph/dqhUvVe0M2em7g/JEn1M2BLOmHb1s0MDQ7Mqw0NDrBt6+aaOjq1bvbcxP0hSaqfFzlKOmH2wr0mzZrRzZ6buD8kSfWLzKy7h0qNjIzk2NhY3W1IkiSpz0XEgcwc6aw7RESSJEmqkAFbkiRJqpABW5IkSaqQAVuSJEmqkAFbkiRJqpABW5IkSaqQAVuSJEmqkAFbkiRJqpB3clSlRg9Oete7Obq1P9zPkiT1LgO2KjN6cJLte8ZpTc8AMDnVYvuecYBVGf66tT/cz5Ik9TaHiKgyu/YdPhH6ZrWmZ9i173BNHdWrW/vD/SxJUm8zYKsyR6daper9rlv7w/0sSVJvM2CrMuvXDpWq97tu7Q/3syRJvc2Arcps27qZocGBebWhwQG2bd1cU0f16tb+cD9LktTbvMhRlZm9wM7ZLQrd2h/uZ0mSeltkZt09VGpkZCTHxsbqbkOSJEl9LiIOZOZIZ90hIpIkSVKFDNiSJElShQzYkiRJUoUM2JIkSVKFDNiSJElShQzYkiRJUoUM2JIkSVKFDNiSJElShQzYkiRJUoVqu1V6RJwD/C/g+9t9vCszX92xztOBdwOfa5f2ZObOFWxT6knXjo5zy+1HmMlkIIIrL9zI71/++J7f9ujBSW/x3ua+kKT+VVvABr4NPDMz74uIQeDvI+J9mXlbx3ofzcxLauhP6knXjo5z8213n1ieyTyxfKZBuJvbHj04yfY947SmZwCYnGqxfc84wKoLlu4LSepvtQ0RycJ97cXB9iPr6kdqiltuP1Kq3ivb3rXv8IlAOas1PcOufYfPeNtN476QpP52WmewI+IHgIcA0flaZt59/+9YdDsDwAHgscAfZ+btC6x2UUR8EjgKvDIz/3mB7bwYeDHAIx/5yOX+eKmRZnLhv0MXq/fKto9OtUrV+5n7QpL627LPYEfE90XEqyJiEvg68HmKsdGdj2XLzJnM/ElgGHhyRJzXscodwKMy8yeAPwJGF9nOWzJzJDNH1q1bV6YFqXEG4n5/1y5Z75Vtr187VKrez9wXktTfygwReS3wB8DXgD8Gdi7yKC0zp4CPAD/TUb93dhhJZr4XGIyIh57Oz5D6xZUXbixV75Vtb9u6maHBgXm1ocEBtm3dfMbbbhr3hST1tzJDRJ4PvD8zL67iB0fEOmA6M6ciYgh4FvBfOtZ5OPDlzMyIeDLFHwT3VPHzpaaavdiwGzN9dHPbsxfvOXOG+0KS+l3kMsdWRkQLeHlm/mklPzjifOAvgQGK4Lw7M3dGxEsAMvOGiPhN4KXAd4EWcE1m/u+ltjsyMpJjY2NVtChJkiQtKiIOZOZIZ73MGexx4BFVNZSZh4ALFqjfMOfrNwFvqupnSpIkSd1WZgz27wIviYgzH4wpSZIk9alFz2BHxI4Fyl8APhURf0MxY8hMx+uZmb9XYX+SJElSoyw1ROS6JV57/iL1BAzYkiRJWrWWCtjnrlgXkiRJUp9YNGBn5hdWshFJkiSpH5S5k+NdEXHZEq9fEhF3VdOWJEmS1ExlZhHZBDxgidd/EHjUGXUjSZIkNVyZebBP5YeBb1a4PTXQ6MHJxt2d7trR8a7cubCbutlzN4+h7w/1lUO7Yf9OOD4Ba4Zhyw44/4q6u5LUA5YM2BHxNODpc0rPjYjHLrDqg4HnAZ+orDM1zujBSbbvGac1XczeODnVYvuecYCeDVHXjo5z8213n1ieyTyx3Kshqps9d/MY+v5QXzm0G/ZeDdOtYvn4kWIZDNmSTjlE5BkU0/VdRzEF33PnLM99XA3cC/yH6ltUU+zad/hEeJrVmp5h177DNXV0arfcfqRUvRd0s+duHkPfH+or+3eeDNezpltFXdKqd6ohIm8AbgICuAt4OfDujnUSuC8zv1Zxb2qYo1OtUvVeMJNZqt4LutlzN4+h7w/1leMT5eqSVpUlA3ZmHgeOA0TEM4A7M/MrK9GYmmf92iEmFwhL69cO1dDN8gxELBiWBiJq6GZ5utlzN4+h7w/1lTXDxbCQheqSVr1lzyKSmX9nuNZStm3dzNDgwLza0OAA27ZurqmjU7vywo2l6r2gmz138xj6/lBf2bIDBjv+OBwcKuqSVr1Fz2BHxH8/je1lZr7oDPpRg81eqNakWSJmL1Rr0iwR3ey5m8fQ94f6yuyFjM4iImkBkYuMJYyI7y1Qnl258/+PZruWmTlAjUZGRnJsbKzOFiRJkrQKRMSBzBzprC86RCQzv2/ug2Ke609QXOT4b4C17cdTgfcAd7TXkSRJklatMndy/EPgK5n53My8LTPvbT8+lpk/B3wVeF132pQkSZKaoUzA/llg7xKv7wUuPrN2JEmSpGYrE7C/H1hq/qHh9jqSJEnSqlUmYP898Fvt26fPExE/BfwW8A9VNSZJkiQ10anu5DjXNRQh+8MRMQb8C8XsIT8GjFDcKv0VlXcoSZIkNciyA3ZmfioingD8AXAJ8KT2S/cB/wO4NjPvqr5FSZIkqTnKnMEmMz8P/GJEBPAwirmvv5KZC82ZLUmSJK06pQL2rCzuTvPlinuRJEmSGm+pW6U/EiAz7567fCqz60vqntGDk1275Xg3ty2pjx3a7a3jpbalzmB/HvheRPxAZn6nvbzwfdXnq/VW6VK/Gz04yfY947SmZwCYnGqxfc84wBkH4W5uW1IfO7Qb9l4N061i+fiRYhkM2VqVlgrYOykC9Xc7liXVaNe+wycC8KzW9Ay79h0+4xDczW1L6mP7d54M17OmW0XdgK1VaNGAnZnXLbUsqR5Hp1ql6r2ybUl97PhEubrU58rcaEZSD1i/dqhUvVe2LamPrVnkRs+L1aU+t+yAHRH/FBFvjIjLI2JtF3uStIRtWzczNDj/UoehwQG2bd3c09uW1Me27IDBjj/EB4eKurQKlZmm7xvAb1DcEn0mIj4JfKj9+GhmfqML/UnqMDsWuhszfXRz25L62Ow4a2cRkQCIYkrrZa4c8UDg6cAz2o/zKW42Mw38I7A/M19dfZvLNzIykmNjY3W2IEmSpFUgIg5k5khnvdQY7Mz8embuzcxrMvMCYB3wy8CngX8DXFtJt5IkSVJDlb6TY0R8H/Ak4JnAFopgfQ7wJYrhIpIkSdKqteyAHRFXUwTqnwIeBPwf4O+AbcCHMvPOrnQoSZIkNUiZM9hvAGaAdwBvBA5mmQHckiRJ0ipQZgz2B4FvU4y5/p/AzRHxoog4tyudSZIkSQ207DPYmfnTETEIPIViqMgzgD8GBiPiborx1/sz8x1d6VSSJElqgLKziExn5kcz87rM/Cngh4ArgW8CVwFvq75FSZIkqTlOZxaRIeDfUswi8kzgCcAA8D3gE1U2J0mSJDVNmVlEdlAMDbkQGKS4wcydwA0Uw0M+nJlTXehx1Ro9ONm4O+p1s+drR8e55fYjzGQyEMGVF27k9y9/fCXbbpomvjekWhza7d0Fm85jqMX08HujzBns64DPUQwD+RDF1Hxf7kZTKgLU9j3jtKZnAJicarF9zzhAzwapbvZ87eg4N99294nlmcwTy6stZDfxvSHV4tBu2Hs1TLeK5eNHimXomX+EdQoeQy2mx98bZcZgb8rMx2Tmr2XmLYbr7tq17/CJADWrNT3Drn2Ha+ro1LrZ8y23HylV72dNfG9Itdi/8+Q/vrOmW0VdzeAx1GJ6/L2x7ICdmXefei1V5ehUq1S9F3Sz55lFplxfrN7PmvjekGpxfKJcXb3HY6jF9Ph7o9QsIlo569cOlar3gm72PBBRqt7PmvjekGqxZrhcXb3HY6jF9Ph7w4Ddo7Zt3czQ4MC82tDgANu2bq6po1PrZs9XXrixVL2fNfG9IdViyw4Y7PjDc3CoqKsZPIZaTI+/N0pP06eVMXuxWpNmiuhmz7MXMjqLSDPfG1ItZi906tFZBrQMHkMtpsffG5F9NoZ1ZGQkx8bG6m5DkiRJfS4iDmTmSGfdISKSJElShQzYkiRJUoUWHYPdvnNjWZmZv3cG/UiSJEmNttRFjtedxvYSMGBLkiRp1VoqYJ+7Yl1IkiRJfWLRgJ2ZX1jJRiRJkqR+4EWOkiRJUoVK32gmIkaAC4Ef4v4B3YscJUmStKotO2BHxBCwB/hpICguaIz2yzmnZsCWJEnSqlXmDPYOinD9n4H9wIeBXwG+AmwHhoAXVN2gmmX04GTjbuHdzZ6vHR339u6SpOrceg0cuAlyBmIAnngVXPK6urta2qHdPXtL824pMwb7F4C/yswdwD+1a5OZuQ94FnA2cFW17alJRg9Osn3POJNTLRKYnGqxfc84owcn625tUd3s+drRcW6+7W5mMgGYyeTm2+7m2tHxM962JGkVuvUaGLuxCNdQPI/dWNR71aHdsPdqOH4EyOJ579VFvY+VCdgbgb9rf90+spwNkJnfBW4Bnldda2qaXfsO05qemVdrTc+wa9/hmjo6tW72fMvtR0rVJUla0oGbytV7wf6dMN2aX5tuFfU+ViZgf52TQ0q+DnwPWD/n9ePAwyvqSw10dKpVqt4Lutnz7Jnr5dYlSVpSzpSr94LjE+XqfaJMwP4s8KMAmTkD/DPFsBEiIoDnAp6aW8XWrx0qVe8F3ex5IKJUXZKkJcVAuXovWDNcrt4nygTsDwI/H3HiKP4p8DMR8Vng0xTjsG+suD81yLatmxkanP8hHxocYNvWzTV1dGrd7PnKCzeWqkuStKQnXlWu3gu27IDBjpNWg0NFvY+VmUXktcDbaE/Nl5l/EhHnAM+nGJP9Z8B/rbxDNcbszBtNmkWkmz3PzhbiLCKSpErMzhbSpFlEZmcLWWWziET22XjQkZGRHBsbq7sNSZIk9bmIOJCZI511b5UuSZIkVahUwI6IcyLidyLiYxHx5fbjY+1a717JJkmSJK2QMrdKXwd8CHgccC9wF8V47B8DLgReEBHPyMxj3WhUkiRJaoIyZ7B3AT8OXAM8LDOfkJkXAA8DXkERtHdV36IkSZLUHGVmEbkUuDEz3zC3mJnfAV4fEY8Dfq7C3iRJkqTGKXMG+2zgjiVeH2uvI0mSJK1aZQL2PwJPWOL1JwIfP7N2JEmSpGYrM0TkFcD+iBgHbsjMaYCIOAt4GcWt0rdU36IkSZLUHGUC9h8C9wBvAHZGxF1AAo8BHgR8FnhdRMz9nszMBUN3+y6Q/wv4/nYf78rMV3esE8AbgYuBbwJXZeZSw1RqMXpwsit3AuzWdjXftaPjXbvbou+NPnBod/PuQHbrNd2501sT94U9qw7dPIa+PxqhTMB+NEWgvru9/OD281T7MQicW2J73waemZn3RcQg8PcR8b7MvG3OOs8GfqT9uBB4c/u5Z4wenGT7nnFa0zMATE612L5nHOCMAk+3tqv5rh0d5+bb7j6xPJN5YvlMQ7bvjT5waDfsvRqmW8Xy8SPFMvTuP2i3XgNjN55czpmTy2cSspu4L+xZdejmMfT90RjLHoOdmZsy89yyjyW2l5l5X3txsP3ovG/7c4C3tte9DVgbEY8o+0t20659h08EnVmt6Rl27Tvck9vVfLfcfqRUvQzfG31g/86T/5DNmm4V9V514KZy9eVq4r6wZ9Whm8fQ90dj1Hqr9IgYiIhPAF8BPpCZt3essgGYm3Qm2rXO7bw4IsYiYuzYsZW9z83RqVapet3b1Xwz2fk33dL1Mnxv9IHjE+XqvSBnytWXq4n7wp5Vh24eQ98fjVE6YEfEuRHx7yPiP0XEpnbt7Ih4ZESUmqYvM2cy8yeBYeDJEXFe549b6NsW2M5bMnMkM0fWrVtXpoUztn7twneIX6xe93Y130As9BZbvF6G740+sGa4XL0XxEC5+nI1cV/Ys+rQzWPo+6MxSgXsiPgvwL8CbwF2UozLBjgH+BTwG6fTRGZOAR8BfqbjpQlg45zlYeDo6fyMbtm2dTNDg/P/4RoaHGDb1s09uV3Nd+WFG0vVy/C90Qe27IDBjj9cBoeKeq964lXl6svVxH1hz6pDN4+h74/GWHbAjohfB7YBfwz8NHPOLmfmvcB7KO72uNztrYuIte2vh4BnAf/Ssdp7gBdE4SnA8cz84nJ/xkq4/IINvOa5j2fD2iEC2LB2iNc89/FnfLFZt7ar+X7/8sfz/Kc88sQZ64EInv+UR1Yyi4jvjT5w/hVw6fWwZiMQxfOl1/f2xUSXvA5GXnTyjHUMFMtnOotIE/eFPasO3TyGvj8aI3KZY00j4pPAZzLz5yPiIcAx4FmZ+aH2668CfjMzl/X/KSLifOAvgQGKoL87M3dGxEsAMvOG9jR9b6I4s/1N4Fczc2yp7Y6MjOTY2JKrSJIkSWcsIg5k5khnvcw0fT9KMU3eYo4BD13uxjLzEHDBAvUb5nydFDexkSRJkhqhzBjsbwE/uMTrj6KYD1uSJElatcoE7I8DP7fQC+27Mv4y8A9VNCVJkiQ1VZmAvQu4KCLeBpzfrj08IrZSzAAyDPy3atuTJEmSmmXZY7Az84MR8VLgjcAvtstvaz9/B/i1zPxYxf1JkiRJjVLmIkcy8y0R8R7g/wb+L4qp+j5NMQPIZBf6kyRJkhqlVMAGyMwvAX/UhV4kSZKkxisdsOeKiLOA5wAPBva2w7ckSZK0apW5k+N/jYh/nLMcwAeB3cCfAuMR8ZjqW5QkSZKao8wsIj8DfHTO8qXA0yhmF5m96PFVFfUlYPTgJE997Yc491X/k6e+9kOMHnSYu6RlOLQbXn8eXLe2eD60u7e321RN3M9NPIb2rAYqM0RkI8UFjbMuBT6Xma8CiIjHAb9UYW+r2ujBSbbvGac1PQPA5FSL7XvGAbj8gg11tiaplx3aDXuvhulWsXz8SLEMcP4Vvbfdpmrifm7iMbRnNVSZM9hnAzNzlp9BMURk1l3AI6poSrBr3+ET4XpWa3qGXfsO19SRpEbYv/PkP+yzpltFvRe321RN3M9NPIb2rIYqE7CPAE+BE2erHw383ZzXHwbcV11rq9vRqVapuiQBcHyiXL3u7TZVE/dzE4+hPauhygTsdwK/EhG3ArcC9wLvnfP6BcBnK+xtVVu/dqhUXZIAWDNcrl73dpuqifu5icfQntVQZQL2a4CbgIuABF6QmVMAEbEGuAzYX3F/q9a2rZsZGhyYVxsaHGDb1s01dSSpEbbsgMGOP8QHh4p6L263qZq4n5t4DO1ZDVXmVunfBl7UfnT6OsX4629W1NeqN3sh4659hzk61WL92iG2bd3sBY6SljZ7EdX+ncX/kl4zXPzDfqYXV3Vru03VxP3cxGNoz2qoyMy6e6jUyMhIjo2N1d2GJEmS+lxEHMjMkc56mSEikiRJkk7BgC1JkiRVyIAtSZIkVciALUmSJFXIgC1JkiRVyIAtSZIkVciALUmSJFXIgC1JkiRVaNl3cpQkrXK3XgMHboKcgRiAJ14Fl7yu7q76j/t55Rza7R0XZ7kvKmXAliSd2q3XwNiNJ5dz5uSy4a867ueVc2g37L0aplvF8vEjxTKsvmDpvqicQ0QkSad24KZydZ0e9/PK2b/zZKCcNd0q6quN+6JyBmxJ0qnlTLm6To/7eeUcnyhX72fui8oZsCVJpxYD5eo6Pe7nlbNmuFy9n7kvKmfAliSd2hOvKlfX6XE/r5wtO2BwaH5tcKiorzbui8oZsCVJp3bJ62DkRSfPpMZAseyFd9VyP6+c86+AS6+HNRuBKJ4vvX51XtTnvqhcZGbdPVRqZGQkx8bG6m5DkiRJfS4iDmTmSGfdM9iSJElShQzYkiRJUoUM2JIkSVKFDNiSJElShQzYkiRJUoUM2JIkSVKFDNiSJElShQzYkiRJUoUM2JIkSVKFzqq7AUmryKHdsH8nHJ+ANcOwZYe34u2GJu7nW6+BAzdBzhS3B3/iVb1/e/Am7mdJK8KALWllHNoNe6+G6VaxfPxIsQyGkio1cT/feg2M3XhyOWdOLvdqyG7ifpa0YhwiImll7N95MozMmm4VdVWnifv5wE3l6r2giftZ0ooxYEtaGccnytV1epq4n3OmXL0XNHE/S1oxBmxJK2PNcLm6Tk8T93MMlKv3gibuZ0krxoAtaWVs2QGDQ/Nrg0NFXdVp4n5+4lXl6r2giftZ0ooxYEtaGedfAZdeD2s2AlE8X3q9F4RVrYn7+ZLXwciLTp6xjoFiuVcvcIRm7mdJKyYys+4eKjUyMpJjY2N1tyFJkqQ+FxEHMnOks+4ZbEmSJKlCBmxJkiSpQgZsSZIkqUIGbEmSJKlCBmxJkiSpQgZsSZIkqUIGbEmSJKlCBmxJkiSpQgZsSarDod3w+vPgurXF86HddXd0at3suYn7Q5IWcVbdDUjSqnNoN+y9GqZbxfLxI8Uy9O6ttrvZcxP3hyQtwTPYkrTS9u88GSZnTbeKeq/qZs9N3B+StAQDtiSttOMT5eq9oJs9N3F/SNISDNiStNLWDJer94Ju9tzE/SFJSzBgS9JK27IDBofm1waHinqv6mbPTdwfkrQEA7YkrbTzr4BLr4c1G4Eoni+9vrcv6Otmz03cH5K0hMjMunuo1MjISI6NjdXdhiRJkvpcRBzIzJHOumewJUmSpAoZsCVJkqQKGbAlSZKkChmwJUmSpAoZsCVJkqQKGbAlSZKkChmwJUmSpAoZsCVJkqQKGbAlSZKkCtUWsCNiY0R8OCLujIh/jojfXmCdp0fE8Yj4RPuxo45epVXl0G54/Xlw3dri+dDuujvqT93czx5D1cH3nXTCWTX+7O8Cr8jMOyLigcCBiPhAZn6qY72PZuYlNfQnrT6HdsPeq2G6VSwfP1IsA5x/RX199Ztu7mePoerg+06ap7Yz2Jn5xcy8o/3114E7gQ119SMJ2L/z5D+Qs6ZbRV3V6eZ+9hiqDr7vpHl6Ygx2RGwCLgBuX+DliyLikxHxvoh43CLf/+KIGIuIsWPHjnWzVam/HZ8oV9fp6eZ+9hiqDr7vpHlqD9gR8QDgr4GXZ+a9HS/fATwqM38C+CNgdKFtZOZbMnMkM0fWrVvX1X6lvrZmuFxdp6eb+9ljqDr4vpPmqTVgR8QgRbh+e2bu6Xw9M+/NzPvaX78XGIyIh65wm9LqsWUHDA7Nrw0OFXVVp5v72WOoOvi+k+apcxaRAG4E7szM1y2yzsPb6xERT6bo956V61JaZc6/Ai69HtZsBKJ4vvR6L1KqWjf3s8dQdfB9J80TmVnPD474t8BHgXHge+3yfwQeCZCZN0TEbwIvpZhxpAVck5n/e6ntjoyM5NjYWNf6liRJkgAi4kBmjnTWa5umLzP/HohTrPMm4E0r05EkSZJ05mq/yFGSJEnqJwZsSZIkqUIGbEmSJKlCBmxJkiSpQgZsSZIkqUIGbEmSJKlCBmxJkiSpQrXNgy2tCod2w/6dcHwC1gwXtw32zmYCuPUaOHAT5AzEADzxKrhkwZvaSpIaxoAtdcuh3bD3aphuFcvHjxTLYMhe7W69BsZuPLmcMyeXDdmS1HgOEZG6Zf/Ok+F61nSrqGt1O3BTubokqVEM2FK3HJ8oV9fqkTPl6pKkRjFgS92yZrhcXatHDJSrS5IaxYAtdcuWHTA4NL82OFTUtbo98apydUlSoxiwpW45/wq49HpYsxGI4vnS673AUcWFjCMvOnnGOgaKZS9wlKS+EJlZdw+VGhkZybGxsbrbkCRJUp+LiAOZOdJZ9wy2JEmSVCEDtiRJklQhA7YkSZJUIQO2JEmSVCEDtiRJklQhA7YkSZJUIQO2JEmSVCEDtiRJklQhA7YkSZJUobPqbkD1GD04ya59hzk61WL92iG2bd3M5RdsqLstLdeh3bB/JxyfgDXDsGWHt2BvGo+h+o3vaekEA/YqNHpwku17xmlNzwAwOdVi+55xAEN2ExzaDXuvhulWsXz8SLEM/mPWFB5D9Rvf09I8DhFZhXbtO3wiXM9qTc+wa9/hmjpSKft3nvxHbNZ0q6irGTyG6je+p6V5DNir0NGpVqm6eszxiXJ19R6PofqN72lpHgP2KrR+7VCpunrMmuFydfUej6H6je9paR4D9iq0betmhgYH5tWGBgfYtnVzTR2plC07YLDjj6HBoaKuZvAYqt/4npbm8SLHVWj2QkZnEWmo2QuGvFq/uTyG6je+p6V5IjPr7qFSIyMjOTY2VncbkiRJ6nMRcSAzRzrrDhGRJEmSKmTAliRJkipkwJYkSZIqZMCWJEmSKmTAliRJkipkwJYkSZIqZMCWJEmSKmTAliRJkipkwJYk6XQc2g2vPw+uW1s8H9pdd0en1sSepQbyVumSJJV1aDfsvRqmW8Xy8SPFMvTu7cGb2LPUUJ7BliSprP07TwbVWdOtot6rmtiz1FAGbEmSyjo+Ua7eC5rYs9RQBmxJkspaM1yu3gua2LPUUAZsSZLK2rIDBofm1waHinqvamLPUkMZsCVJKuv8K+DS62HNRiCK50uv7+2LBZvYs9RQkZl191CpkZGRHBsbq7sNSZIk9bmIOJCZI511z2BLkiRJFTJgS5IkSRUyYEuSJEkVMmBLkiRJFTJgS5IkSRUyYEuSJEkVMmBLkiRJFTJgS5IkSRUyYEuSJEkVMmBLkiRJFTJgS5IkSRUyYEuSJEkVMmBLkiRJFTJgS5IkSRUyYEuSJEkVMmBLkiRJFTJgS5IkSRUyYEuSJEkVMmBLkiRJFTJgS5IkSRUyYEuSJEkVMmBLkiRJFTJgS5IkSRUyYEuSJEkVMmBLkiRJFaotYEfExoj4cETcGRH/HBG/vcA6ERHXR8RnIuJQRDyhjl6lnnNoN7z+PLhubfF8aHfdHUmSpLazavzZ3wVekZl3RMQDgQMR8YHM/NScdZ4N/Ej7cSHw5vaztHod2g17r4bpVrF8/EixDHD+FfX1JUmSgBrPYGfmFzPzjvbXXwfuBDZ0rPYc4K1ZuA1YGxGPWOFWpd6yf+fJcD1rulXUJUlS7XpiDHZEbAIuAG7veGkDcGTO8gT3D+FExIsjYiwixo4dO9a1PqWecHyiXF2SJK2o2gN2RDwA+Gvg5Zl5b+fLC3xL3q+Q+ZbMHMnMkXXr1nWjTal3rBkuV5ckSSuq1oAdEYMU4frtmblngVUmgI1zloeBoyvRm9SztuyAwaH5tcGhoi5JkmpX5ywiAdwI3JmZr1tktfcAL2jPJvIU4HhmfnHFmpR60flXwKXXw5qNQBTPl17vBY6SJPWIOmcReSrwy8B4RHyiXfuPwCMBMvMG4L3AxcBngG8Cv7rybUo96PwrDNSSJPWo2gJ2Zv49C4+xnrtOAi9bmY4kSZKkM1f7RY6SJElSPzFgS5IkSRUyYEuSJEkVMmBLkiRJFTJgS5IkSRUyYEuSJEkVMmBLkiRJFTJgS5IkSRUyYEuSJEkVMmBLkiRJFTJgS5IkSRUyYEuSJEkVMmBLkiRJFTJgS5IkSRWKzKy7h0pFxDHgC3X30SAPBb5adxM6bR6/5vMYNp/HsPk8hs1W5/F7VGau6yz2XcBWORExlpkjdfeh0+Pxaz6PYfN5DJvPY9hsvXj8HCIiSZIkVciALUmSJFXIgK231N2AzojHr/k8hs3nMWw+j2Gz9dzxcwy2JEmSVCHPYEuSJEkVMmBLkiRJFTJgrxIRMRARByPi1gVee3pEHI+IT7QfO+roUYuLiM9HxHj7+Iwt8HpExPUR8ZmIOBQRT6ijTy1uGcfQz2GPi4i1EfGuiPiXiLgzIi7qeN3PYQ9bxvHzM9jDImLznGPziYi4NyJe3rFOz3wGz6rrB2vF/TZwJ/CgRV7/aGZesoL9qLxnZOZiE+k/G/iR9uNC4M3tZ/WWpY4h+DnsdW8E3p+ZvxARZwM/0PG6n8PedqrjB34Ge1ZmHgZ+EoqThsAk8Dcdq/XMZ9Az2KtARAwDPwv8ed29qGueA7w1C7cBayPiEXU3JfWLiHgQ8DTgRoDM/E5mTnWs5uewRy3z+Kk5tgCfzczOO3f3zGfQgL06vAH4HeB7S6xzUUR8MiLeFxGPW5m2VEICfxsRByLixQu8vgE4Mmd5ol1T7zjVMQQ/h73s0cAx4C/aw+3+PCJ+sGMdP4e9aznHD/wMNsXzgFsWqPfMZ9CA3eci4hLgK5l5YInV7gAelZk/AfwRMLoSvamUp2bmEyj+99fLIuJpHa/HAt/jHJy95VTH0M9hbzsLeALw5sy8APgG8KqOdfwc9q7lHD8/gw3QHt5zGfBXC728QK2Wz6ABu/89FbgsIj4PvBN4ZkTcPHeFzLw3M+9rf/1eYDAiHrrinWpRmXm0/fwVijFnT+5YZQLYOGd5GDi6Mt1pOU51DP0c9rwJYCIzb28vv4sisHWu4+ewN53y+PkZbIxnA3dk5pcXeK1nPoMG7D6XmdszczgzN1H8L5UPZebz564TEQ+PiGh//WSK98U9K96sFhQRPxgRD5z9Gvhp4J86VnsP8IL2FdRPAY5n5hdXuFUtYjnH0M9hb8vMLwFHImJzu7QF+FTHan4Oe9Ryjp+fwca4koWHh0APfQadRWSVioiXAGTmDcAvAC+NiO8CLeB56S0+e8kPA3/T/u/+WcA7MvP9HcfwvcDFwGeAbwK/WlOvWthyjqGfw973W8Db2/+L+i7gV/0cNsqpjp+fwR4XET8A/Dvg1+fUevIz6K3SJUmSpAo5RESSJEmqkAFbkiRJqpABW5IkSaqQAVuSJEmqkAFbkiRJqpABW5L6UERsioiMiOuWse7T2+te1f3OqhMRV7X7fnrdvUjSXAZsSVLPioifjIjrImJT3b1I0nIZsCVJvewngVcDm+ptQ5KWz4AtSZIkVciALUnLFBHntIcrHI6Ib0bEVESMR8SuBdZ9VkT8bXudb0XEodlb+nas9/mI+EhEPCEiPhQR90XE1yLiLyPiYR3rPjAifj8ibo+Ir0bEtyPiMxHx2vYthKv+fSMiXhoRB9q/79cj4sMR8YyO9U6M946ISyLiH9u/8xcjYldEnLXAtn8+Ij7ZXu/uiHh1e5+dGAveHj/+F+1v+XD7tYyImzo2930R8cqI+Gx7n/xrRPxK1ftDkpbrfv/RkyQt6o+BFwJvBV4PDAA/Ajxz7koR8WLgBuA24D8D3wD+HfDmiHhMZm7r2O4wsB/4a+BdwBPaP2ckIp6Umd9sr7cB+Pft9d4BfBf4KeB3gAuArVX+ssDbgCvbPf0F8P3ALwEfiIjnZuZ7Ota/GPgNit/9vwPPAV4J/B/gD2ZXioj/B7gF+Czwu+3f41eASzu2twd4BPDi9vff2a5/tmO9PwCGgD8Fvg28FLgpIj6Tmf9wOr+4JJ2RzPThw4cPH8t4AF8D3nuKdR4BfAt4xwKvvRGYAR4zp/Z5IIGXd6z7H9r1V82pnQ0MLrDd32uv++Q5tU3t2nXL+L2e3l73qjm1n2vXXtyx7lnAGPA5IDp+1jeATXPWDeCfgC92fP8k8GXgh+bUHwDctUAfV7VrT1+g79nXDgJnz6lvoAjat9T9nvHhw8fqfDhERJKW7zjwuIg4b4l1foHiTO+NEfHQuQ9gL8XQvC0d33Mv8OaO2p+06z83W8jM72TmNEBEnBURP9Te7gfbq1x4ur/YAp4PfB0Y7fgd1rZ/j00UZ+/nGs3Mz8/pN4EPAw+PiAe0y08E1gM3Zeb/mbPufRRnvk/Hn2Tmd+ZsaxL41wX6k6QV4RARSVq+l1MMmxiPiLsowuNeYG9mfq+9zo+1nz94/28/4Yc7lu/KzG/PLWTmt9s/49Fz6xHxG8BLgMdx/+tofmiZv8dy/BjwQIozzYv5YYogO+uuBda5p/38EOA+4Nz28uEF1l2othyL/dxHneb2JOmMGLAlaZky893t+Zgvphj7/CzgRcBHI+JZ7bOo0V79BcAXF9lUZyDMRdaLeQsR1wB/CPwtcD1wFPgOxZCIm6j2wvUAjgG/uMQ6/9SxPHOK7c19rtJiP7cbP0uSTsmALUklZObXgJuBmyMigNdSXGT4HOCvgE+3V/1qZi51Fnuux0TE2XOHOUTE91Oc7f2XOev9MsWY7WfPOWNORPzMaf46S/k08KPAbe3hG1X5XPt58wKvLVRb7I8PSepZjsGWpGWIiIGIWDu31h5jfLC9+OD2826KC+x+NyKGFtjOmnZ4nutBFLNvzPUb7fronNoMReA8cWa2PQXeq8r8Lsv0Vop/I16z0IsR0TnMZbnGKM7sXxURJ4a0tMdo328aQ4phJXBy/0pSz/MMtiQtzwOBL0bEeyhC9VcozjC/lGIaur0AmTkRES8F/hy4MyLeBnwBWAc8Hrgc+HGKM9GzPgu8un3x5AGKCwFfSHH2+vo5672LIvC+LyL2UATwXwSmq/5lM/NdEfEXwG9GxBOAW4GvUkwpeBHwWDrGhy9zu9+NiFcCbwc+HhE3UkzTdxXFuOlzmX/W+h+B7wH/qR3IvwF8LjNvP93fTZK6zYAtScvzTeANFDOAPItiWrkvAu8BXpOZR2dXzMy/iIh/pZgD+tcpZt74KsVFfP8f8KWObU8AVwD/jWLe6e9QBNBXZuY35qy3i+Ls9Ysopvz7EvA/KOao/lRlv+nJ3+OFEfFhinmot1NME/gl4I728ulu9x0R8V3gWop5sL8M3Agcopj7ujVn3bsj4oXA/0sx08og8JeAAVtSz5qdw1SSVIOI+Dzw+cx8es2t1C4iXkHxR8ZFmXlb3f1I0ulyDLYkaUVFxNkRMdBRewDwMophInfU0pgkVcQhIpKklfZoinHk76SYVeQRFLdKPxd46dzZVCSpiQzYkqSVdgy4Dfgl4GEUFzmOU9wWfnedjUlSFRyDLUmSJFXIMdiSJElShQzYkiRJUoUM2JIkSVKFDNiSJElShQzYkiRJUoX+fyIuePTXkmoBAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 864x576 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.figure(figsize=(12, 8))\n",
    "plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')\n",
    "plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')\n",
    "plt.xlabel('sepal length', fontsize=18)\n",
    "plt.ylabel('sepal width', fontsize=18)\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Numpy实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "class KNN:\n",
    "\n",
    "    def __init__(self, X_train, y_train, n_neighbors=3, p=2):\n",
    "        \"\"\"\n",
    "        parameter: n_neighbors 临近点个数\n",
    "        parameter: p 距离度量\n",
    "        \"\"\"\n",
    "        self.n = n_neighbors\n",
    "        self.p = p\n",
    "        self.X_train = X_train\n",
    "        self.y_train = y_train\n",
    "\n",
    "    # 对给定的输入数据进行预测\n",
    "    def predict(self, X):\n",
    "        # 取出n个点\n",
    "        knn_list = []\n",
    "        for i in range(self.n):\n",
    "            # 计算输入数据和训练样本之间的距离\n",
    "            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)\n",
    "            # 将距离和对应的训练样本标签添加到knn_list中\n",
    "            knn_list.append((dist, self.y_train[i]))\n",
    "\n",
    "        # 对于训练集中不在前n个最近邻中的样本，找到距离最近的前n个邻居中出现次数最多的类别\n",
    "        for i in range(self.n, len(self.X_train)):\n",
    "            # 找到距离最大的点的索引\n",
    "            max_index = knn_list.index(max(knn_list, key=lambda x: x[0]))\n",
    "            # 计算输入数据和训练样本之间的距离\n",
    "            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)\n",
    "            # 如果当前样本的距离比最大距离小，则替换最大距离的样本\n",
    "            if knn_list[max_index][0] > dist:\n",
    "                knn_list[max_index] = (dist, self.y_train[i])\n",
    "\n",
    "        # 统计每个类别的出现次数\n",
    "        knn = [k[-1] for k in knn_list]\n",
    "        count_pairs = Counter(knn)\n",
    "        # 找到出现次数最多的类别\n",
    "        max_count = sorted(count_pairs.items(), key=lambda x: x[1])[-1][0]\n",
    "        return max_count\n",
    "\n",
    "    def score(self, X_test, y_test):\n",
    "        right_count = 0  # 初始化正确预测的数量为0\n",
    "        n = 10  # 设置每个样本最多考虑的最近邻居数量为10\n",
    "        for X, y in zip(X_test, y_test):  # 对于测试集中的每一个样本和标签\n",
    "            label = self.predict(X)  # 使用模型进行预测\n",
    "            if label == y:  # 如果预测结果与真实标签相同\n",
    "                right_count += 1  # 则正确预测的数量加1\n",
    "        return right_count / len(X_test)  # 返回模型在测试集上的准确率"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = np.array(df.iloc[:150, [0, 1, -1]])\n",
    "X, y = data[:,:-1], data[:,-1]\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "clf = KNN(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7777777777777778"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clf.score(X_test, y_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test Point: 2.0\n"
     ]
    }
   ],
   "source": [
    "test_point = [6.0, 3.0]\n",
    "print('Test Point: {}'.format(clf.predict(test_point)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Scikit-learn实例\n",
    "#### sklearn.neighbors.KNeighborsClassifier\n",
    "\n",
    "- n_neighbors: 临近点个数，即k的个数，默认是5\n",
    "- p: 距离度量，默认\n",
    "- algorithm: 近邻算法，可选{'auto', 'ball_tree', 'kd_tree', 'brute'}\n",
    "- weights: 确定近邻的权重\n",
    "\n",
    "- n_neighbors ： int，optional(default = 5)\n",
    "默认情况下kneighbors查询使用的邻居数。就是k-NN的k的值，选取最近的k个点。\n",
    "\n",
    "- weights ： str或callable，可选(默认=‘uniform’)\n",
    "默认是uniform，参数可以是uniform、distance，也可以是用户自己定义的函数。uniform是均等的权重，就说所有的邻近点的权重都是相等的。distance是不均等的权重，距离近的点比距离远的点的影响大。用户自定义的函数，接收距离的数组，返回一组维数相同的权重。\n",
    "- algorithm ： {‘auto’，‘ball_tree’，‘kd_tree’，‘brute’}，可选\n",
    "快速k近邻搜索算法，默认参数为auto，可以理解为算法自己决定合适的搜索算法。除此之外，用户也可以自己指定搜索算法ball_tree、kd_tree、brute方法进行搜索，brute是蛮力搜索，也就是线性扫描，当训练集很大时，计算非常耗时。kd_tree，构造kd树存储数据以便对其进行快速检索的树形数据结构，kd树也就是数据结构中的二叉树。以中值切分构造的树，每个结点是一个超矩形，在维数小于20时效率高。ball tree是为了克服kd树高纬失效而发明的，其构造过程是以质心C和半径r分割样本空间，每个节点是一个超球体。\n",
    "\n",
    "- leaf_size ： int，optional(默认值= 30)\n",
    "默认是30，这个是构造的kd树和ball树的大小。这个值的设置会影响树构建的速度和搜索速度，同样也影响着存储树所需的内存大小。需要根据问题的性质选择最优的大小。\n",
    "\n",
    "- p ： 整数，可选(默认= 2)\n",
    "距离度量公式。在上小结，我们使用欧氏距离公式进行距离度量。除此之外，还有其他的度量方法，例如曼哈顿距离。这个参数默认为2，也就是默认使用欧式距离公式进行距离度量。也可以设置为1，使用曼哈顿距离公式进行距离度量。\n",
    "\n",
    "- metric ： 字符串或可调用，默认为’minkowski’\n",
    "用于距离度量，默认度量是minkowski，也就是p=2的欧氏距离(欧几里德度量)。\n",
    "\n",
    "- metric_params ： dict，optional(默认=None)\n",
    "距离公式的其他关键参数，这个可以不管，使用默认的None即可。\n",
    "\n",
    "- n_jobs ： int或None，可选(默认=None)\n",
    "并行处理设置。默认为1，临近点搜索并行工作数。如果为-1，那么CPU的所有cores都用于并行工作。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.neighbors import KNeighborsClassifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "不同k(n_neighbors)值下的结果："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "KNeighborsClassifier(n_neighbors=3)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clf_sk = KNeighborsClassifier(n_neighbors=3)\n",
    "clf_sk.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7777777777777778"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clf_sk.score(X_test, y_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clf_sk = KNeighborsClassifier(n_neighbors=4)\n",
    "clf_sk.fit(X_train, y_train)\n",
    "clf_sk.score(X_test, y_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7555555555555555"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clf_sk = KNeighborsClassifier(n_neighbors=5)\n",
    "clf_sk.fit(X_train, y_train)\n",
    "clf_sk.score(X_test, y_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "自动调参吧，试试循环，找到最优的k值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "best_k = 2\n",
      "best_score = 0.8\n"
     ]
    }
   ],
   "source": [
    "best_score = 0.0\n",
    "best_k = -1\n",
    "for k in range(1, 11):\n",
    "    knn_clf = KNeighborsClassifier(n_neighbors=k)\n",
    "    knn_clf.fit(X_train, y_train)\n",
    "    score = knn_clf.score(X_test, y_test)\n",
    "    if score > best_score:\n",
    "        best_k = k\n",
    "        best_score = score\n",
    "\n",
    "print(\"best_k = \" + str(best_k))\n",
    "print(\"best_score = \" + str(best_score))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## KD树的划分和搜索\n",
    "\n",
    "### KD树\n",
    "\n",
    "KD树(K-Dimension Tree)，，也可称之为$k$维树，可以用更高的效率来对空间进行划分，并且其结构非常适合寻找最近邻居和碰撞检测。KD树是一种便于对$k$维空间中的数据进行快速检索的数据结构。KD树是二叉树，表示对$k$维空间的一个划分，其每个结点对应于$k$维空间划分中的一个超矩形区域。利用KD树可以省去对大部分数据点的搜索，从而减少搜索的计算量。\n",
    "\n",
    "KD树是二叉树，表示对𝑘维空间的一个划分(partition)。构造KD树相当于不断地用垂直于坐标轴的超平面将𝑘维空间切分，构成一系列的$k$维超矩形区域。KD树的每个结点对应于一个$k$维超矩形区域。\n",
    "\n",
    "### 构造KD树的方法\n",
    "\n",
    "构造根结点，使根结点对应于$k$维空间中包含所有实例点的超矩形区域；\n",
    "\n",
    "通过下面的递归方法，不断地对$k$维空间进行切分，生成子结点。\n",
    "\n",
    "在超矩形区域(结点)上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域(子结点)；\n",
    "\n",
    "这时，实例被分到两个子区域。这个过程直到子区域内没有实例时终止(终止时的结点为叶结点)。\n",
    "\n",
    "在此过程中，将实例保存在相应的结点上。\n",
    "\n",
    "通常，依次选择坐标轴对空间切分，选择训练实例点在选定坐标轴上的中位数(median)为切分点，这样得到的KD树是平衡的。\n",
    "\n",
    "注意，平衡的KD树搜索时的效率未必是最优的。\n",
    "\n",
    "对于构建过程，有两个优化点：\n",
    "\n",
    "1. 选择切分维度\n",
    "\n",
    "根据数据点在各维度上的分布情况，方差越大，分布越分散从方差大的维度开始切分，有较好的切分效果和平衡性。\n",
    "\n",
    "2. 确定中值点\n",
    "\n",
    "预先对原始数据点在所有维度进行一次排序，存储下来，然后在后续的中值选择中，无须每次都对其子集进行排序，提升了性能。也可以从原始数据点中随机选择固定数目的点，然后对其进行排序，每次从这些样本点中取中值，来作为分割超平面。该方式在实践中被证明可以取得很好性能及很好的平衡性。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import namedtuple\n",
    "from pprint import pformat\n",
    "\n",
    "class Node(namedtuple('Node', 'location left_child right_child')):\n",
    "    def __repr__(self):\n",
    "        return pformat(tuple(self))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "# kd-tree每个结点中主要包含的数据结构如下\n",
    "class KdNode(object):\n",
    "    def __init__(self, dom_elt, split, left, right):\n",
    "        self.dom_elt = dom_elt  # k维向量节点(k维空间中的一个样本点)\n",
    "        self.split = split  # 整数（进行分割维度的序号）\n",
    "        self.left = left  # 该结点分割超平面左子空间构成的kd-tree\n",
    "        self.right = right  # 该结点分割超平面右子空间构成的kd-tree\n",
    "\n",
    "\n",
    "class KdTreeCreate(object):\n",
    "    def __init__(self, data):\n",
    "        k = len(data[0])  # 数据维度\n",
    "\n",
    "        def CreateNode(split, data_set):  # 按第split维划分数据集exset创建KdNode\n",
    "            if not data_set:  # 数据集为空\n",
    "                return None\n",
    "            # key参数的值为一个函数，此函数只有一个参数且返回一个值用来进行比较\n",
    "            # operator模块提供的itemgetter函数用于获取对象的哪些维的数据，参数为需要获取的数据在对象中的序号\n",
    "            #data_set.sort(key=itemgetter(split)) # 按要进行分割的那一维数据排序\n",
    "            data_set.sort(key=lambda x: x[split])\n",
    "            split_pos = len(data_set) // 2  # //为Python中的整数除法\n",
    "            median = data_set[split_pos]  # 中位数分割点\n",
    "            split_next = (split + 1) % k  # cycle coordinates\n",
    "\n",
    "            # 递归的创建kd树\n",
    "            return KdNode(\n",
    "                median,\n",
    "                split,\n",
    "                CreateNode(split_next, data_set[:split_pos]),  # 创建左子树\n",
    "                CreateNode(split_next, data_set[split_pos + 1:]))  # 创建右子树\n",
    "\n",
    "        self.root = CreateNode(0, data)  # 从第0维分量开始构建kd树,返回根节点\n",
    "\n",
    "# KDTree的前序遍历\n",
    "def preorder(root):\n",
    "    print(root.dom_elt)\n",
    "    if root.left:  # 节点不为空\n",
    "        preorder(root.left)\n",
    "    if root.right:\n",
    "        preorder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 对构建好的kd树进行搜索，寻找与目标点最近的样本点：\n",
    "from math import sqrt\n",
    "from collections import namedtuple\n",
    "\n",
    "# 定义一个namedtuple,分别存放最近坐标点、最近距离和访问过的节点数\n",
    "result = namedtuple(\"Result_tuple\",\n",
    "                    \"nearest_point  nearest_dist  nodes_visited\")\n",
    "\n",
    "\n",
    "def find_nearest(tree, point):\n",
    "    k = len(point)  # 数据维度\n",
    "\n",
    "    def travel(kd_node, target, max_dist):\n",
    "        if kd_node is None:\n",
    "            return result([0] * k, float(\"inf\"),\n",
    "                          0)  # python中用float(\"inf\")和float(\"-inf\")表示正负无穷\n",
    "\n",
    "        nodes_visited = 1\n",
    "\n",
    "        s = kd_node.split  # 进行分割的维度\n",
    "        pivot = kd_node.dom_elt  # 进行分割的“轴”\n",
    "\n",
    "        if target[s] <= pivot[s]:  # 如果目标点第s维小于分割轴的对应值(目标离左子树更近)\n",
    "            nearer_node = kd_node.left  # 下一个访问节点为左子树根节点\n",
    "            further_node = kd_node.right  # 同时记录下右子树\n",
    "        else:  # 目标离右子树更近\n",
    "            nearer_node = kd_node.right  # 下一个访问节点为右子树根节点\n",
    "            further_node = kd_node.left\n",
    "\n",
    "        temp1 = travel(nearer_node, target, max_dist)  # 进行遍历找到包含目标点的区域\n",
    "\n",
    "        nearest = temp1.nearest_point  # 以此叶结点作为“当前最近点”\n",
    "        dist = temp1.nearest_dist  # 更新最近距离\n",
    "\n",
    "        nodes_visited += temp1.nodes_visited\n",
    "\n",
    "        if dist < max_dist:\n",
    "            max_dist = dist  # 最近点将在以目标点为球心，max_dist为半径的超球体内\n",
    "\n",
    "        temp_dist = abs(pivot[s] - target[s])  # 第s维上目标点与分割超平面的距离\n",
    "        if max_dist < temp_dist:  # 判断超球体是否与超平面相交\n",
    "            return result(nearest, dist, nodes_visited)  # 不相交则可以直接返回，不用继续判断\n",
    "\n",
    "        #----------------------------------------------------------------------\n",
    "        # 计算目标点与分割点的欧氏距离\n",
    "        temp_dist = sqrt(sum((p1 - p2)**2 for p1, p2 in zip(pivot, target)))\n",
    "\n",
    "        if temp_dist < dist:  # 如果“更近”\n",
    "            nearest = pivot  # 更新最近点\n",
    "            dist = temp_dist  # 更新最近距离\n",
    "            max_dist = dist  # 更新超球体半径\n",
    "\n",
    "        # 检查另一个子结点对应的区域是否有更近的点\n",
    "        temp2 = travel(further_node, target, max_dist)\n",
    "\n",
    "        nodes_visited += temp2.nodes_visited\n",
    "        if temp2.nearest_dist < dist:  # 如果另一个子结点内存在更近距离\n",
    "            nearest = temp2.nearest_point  # 更新最近点\n",
    "            dist = temp2.nearest_dist  # 更新最近距离\n",
    "\n",
    "        return result(nearest, dist, nodes_visited)\n",
    "\n",
    "    return travel(tree.root, point, float(\"inf\"))  # 从根节点开始递归"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import process_time\n",
    "from random import random\n",
    "\n",
    "\n",
    "# 产生一个k维随机向量，每维分量值在0~1之间\n",
    "def random_point(k):\n",
    "    return [random() for _ in range(k)]\n",
    "\n",
    "\n",
    "# 产生n个k维随机向量\n",
    "def random_points(k, n):\n",
    "    return [random_point(k) for _ in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time:  6.28125 s\n",
      "Result_tuple(nearest_point=[0.10173282609374357, 0.501003167941415, 0.8000047195369713], nearest_dist=0.002002262336426111, nodes_visited=36)\n"
     ]
    }
   ],
   "source": [
    "N = 400000\n",
    "t0 = process_time()\n",
    "kd2 = KdTreeCreate(random_points(3, N))  # 构建包含四十万个3维空间样本点的kd树\n",
    "ret2 = find_nearest(kd2, [0.1, 0.5, 0.8])  # 四十万个样本点中寻找离目标最近的点\n",
    "t1 = process_time()\n",
    "print(\"time: \", t1 - t0, \"s\")\n",
    "print(ret2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### KD树的绘图代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "from operator import itemgetter\n",
    "\n",
    "def kdtree(point_list, depth=0):\n",
    "    if len(point_list) == 0:\n",
    "        return None\n",
    "    \n",
    "    # 选择“基于深度的轴”，以便轴在所有有效值之间循环\n",
    "    # 只支持二维\n",
    "    axis = depth % 2\n",
    "\n",
    "    # Sort point list and choose median as pivot element\n",
    "    point_list.sort(key=itemgetter(axis))\n",
    "    median = len(point_list) // 2  # 选择中值点\n",
    "    \n",
    "    # 创建节点并构造子树\n",
    "    return Node(\n",
    "        location = point_list[median],\n",
    "        left_child = kdtree(point_list[:median], depth + 1),\n",
    "        right_child = kdtree(point_list[median + 1:], depth + 1)\n",
    "    )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# KD树的线宽\n",
    "line_width = [4., 3.5, 3., 2.5, 2., 1.5, 1., .5, 0.3]\n",
    "\n",
    "\n",
    "def plot_tree(tree, min_x, max_x, min_y, max_y, prev_node, branch, depth=0):\n",
    "    \"\"\" plot K-D tree\n",
    "    :param tree      input tree to be plotted\n",
    "    :param min_x\n",
    "    :param max_x\n",
    "    :param min_y\n",
    "    :param max_y\n",
    "    :param prev_node parent's node\n",
    "    :param branch    True if left, False if right\n",
    "    :param depth     tree's depth\n",
    "    :return tree     node\n",
    "    \"\"\"\n",
    "\n",
    "    cur_node = tree.location  # 当前树节点\n",
    "    left_branch = tree.left_child  # 左分支\n",
    "    right_branch = tree.right_child  # 右分支\n",
    "\n",
    "    #根据树的深度设置线条的宽度\n",
    "    if depth > len(line_width) - 1:\n",
    "        ln_width = line_width[len(line_width) - 1]\n",
    "    else:\n",
    "        ln_width = line_width[depth]\n",
    "\n",
    "    k = len(cur_node)\n",
    "    axis = depth % k\n",
    "\n",
    "    # 画垂直分割线\n",
    "    if axis == 0:\n",
    "        if branch is not None and prev_node is not None:\n",
    "            if branch:\n",
    "                max_y = prev_node[1]\n",
    "            else:\n",
    "                min_y = prev_node[1]\n",
    "\n",
    "        plt.plot([cur_node[0], cur_node[0]], [min_y, max_y],\n",
    "                 linestyle='-',\n",
    "                 color='red',\n",
    "                 linewidth=ln_width)\n",
    "\n",
    "    # 画水平分割线\n",
    "    elif axis == 1:\n",
    "        if branch is not None and prev_node is not None:\n",
    "            if branch:\n",
    "                max_x = prev_node[0]\n",
    "            else:\n",
    "                min_x = prev_node[0]\n",
    "\n",
    "        plt.plot([min_x, max_x], [cur_node[1], cur_node[1]],\n",
    "                 linestyle='-',\n",
    "                 color='blue',\n",
    "                 linewidth=ln_width)\n",
    "\n",
    "    # 画当前节点\n",
    "    plt.plot(cur_node[0], cur_node[1], 'ko')\n",
    "\n",
    "    # 绘制当前节点的左分支和右分支\n",
    "    if left_branch is not None:\n",
    "        plot_tree(left_branch, min_x, max_x, min_y, max_y, cur_node, True,\n",
    "                  depth + 1)\n",
    "\n",
    "    if right_branch is not None:\n",
    "        plot_tree(right_branch, min_x, max_x, min_y, max_y, cur_node, False,\n",
    "                  depth + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_diagram(tree, width, height, min_val, max_val, delta):\n",
    "    plt.figure(\"Kd Tree\", figsize=(width, height))\n",
    "    plt.axis(\n",
    "        [min_val - delta, max_val + delta, min_val - delta, max_val + delta])\n",
    "\n",
    "    plt.grid(b=True, which='major', color='0.75', linestyle='--')\n",
    "    plt.xticks([i for i in range(min_val - delta, max_val + delta, 1)])\n",
    "    plt.yticks([i for i in range(min_val - delta, max_val + delta, 1)])\n",
    "\n",
    "    # 画出树\n",
    "    plot_tree(tree, min_val - delta, max_val + delta, min_val - delta,\n",
    "              max_val + delta, None, None)\n",
    "    plt.title('KD Tree')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def label_nodes(node, i):\n",
    "    loc = node.location\n",
    "\n",
    "    plt.text(loc[0] + 0.15, loc[1] + 0.15, str(i), fontsize=10)\n",
    "\n",
    "    if node.left_child:\n",
    "        i = label_nodes(node.left_child, i + 1)\n",
    "\n",
    "    if node.right_child:\n",
    "        i = label_nodes(node.right_child, i + 1)\n",
    "\n",
    "    return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw_target(point, radius):\n",
    "    plt.plot(point[0], point[1], marker='o', color='#ff007f')\n",
    "    circle = plt.Circle(point,\n",
    "                        0.3,\n",
    "                        facecolor='#ff007f',\n",
    "                        edgecolor='#ff007f',\n",
    "                        alpha=0.5)\n",
    "    plt.gca().add_patch(circle)\n",
    "\n",
    "    # 围绕目标点绘制超球体\n",
    "    circle = plt.Circle(point,\n",
    "                        radius,\n",
    "                        facecolor='#ffd83d',\n",
    "                        edgecolor='#ffd83d',\n",
    "                        alpha=0.5)\n",
    "    plt.gca().add_patch(circle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw_neighbors(point_list):\n",
    "    for point in point_list:\n",
    "        # 画出找到的最近的邻居\n",
    "        plt.plot(point[0], point[1], 'go')\n",
    "        circle = plt.Circle(point,\n",
    "                            0.3,\n",
    "                            facecolor='#33cc00',\n",
    "                            edgecolor='#33cc00',\n",
    "                            alpha=0.5)\n",
    "        plt.gca().add_patch(circle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "from graphviz import Digraph\n",
    "\n",
    "\n",
    "def add_node(dot, node, parent_id=None, i=0, edge_label=''):\n",
    "    loc = node.location\n",
    "    node_id = str(i)\n",
    "    dot.node(node_id, f\"{i}\\n({loc[0]},{loc[1]})\")\n",
    "    if parent_id:\n",
    "        dot.edge(parent_id, node_id, label=edge_label)\n",
    "    if node.left_child:\n",
    "        i = add_node(dot, node.left_child, node_id, i + 1, 'l')\n",
    "    if node.right_child:\n",
    "        i = add_node(dot, node.right_child, node_id, i + 1, 'r')\n",
    "    return i\n",
    "\n",
    "\n",
    "def create_graph(tree):\n",
    "    dot = Digraph(comment='Kd-tree')\n",
    "    dot.attr('node',\n",
    "             fontsize='20',\n",
    "             shape='circle',\n",
    "             width='1',\n",
    "             fixedsize='true')\n",
    "    dot.attr('edge', arrowsize='0.7')\n",
    "    add_node(dot, tree)\n",
    "    return dot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((6, 4),\n",
      " ((4, 5), ((2, 3), None, None), ((5, 7), None, None)),\n",
      " ((9, 6), ((7, 2), None, None), None))\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: %3 Pages: 1 -->\r\n",
       "<svg width=\"260pt\" height=\"326pt\"\r\n",
       " viewBox=\"0.00 0.00 260.00 326.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 322)\">\r\n",
       "<title>%3</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-322 256,-322 256,4 -4,4\"/>\r\n",
       "<!-- 0 -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>0</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"178\" cy=\"-282\" rx=\"36\" ry=\"36\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"178\" y=\"-288\" font-family=\"Times New Roman,serif\" font-size=\"20.00\">0</text>\r\n",
       "<text text-anchor=\"middle\" x=\"178\" y=\"-266\" font-family=\"Times New Roman,serif\" font-size=\"20.00\">(6,4)</text>\r\n",
       "</g>\r\n",
       "<!-- 1 -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>1</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"126\" cy=\"-159\" rx=\"36\" ry=\"36\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-165\" font-family=\"Times New Roman,serif\" font-size=\"20.00\">1</text>\r\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-143\" font-family=\"Times New Roman,serif\" font-size=\"20.00\">(4,5)</text>\r\n",
       "</g>\r\n",
       "<!-- 0&#45;&gt;1 -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>0&#45;&gt;1</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M164.065,-248.574C157.537,-233.384 149.705,-215.159 142.846,-199.2\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"144.988,-197.979 139.974,-192.515 140.486,-199.914 144.988,-197.979\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"158\" y=\"-216.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">l</text>\r\n",
       "</g>\r\n",
       "<!-- 4 -->\r\n",
       "<g id=\"node5\" class=\"node\"><title>4</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"216\" cy=\"-159\" rx=\"36\" ry=\"36\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"216\" y=\"-165\" font-family=\"Times New Roman,serif\" font-size=\"20.00\">4</text>\r\n",
       "<text text-anchor=\"middle\" x=\"216\" y=\"-143\" font-family=\"Times New Roman,serif\" font-size=\"20.00\">(9,6)</text>\r\n",
       "</g>\r\n",
       "<!-- 0&#45;&gt;4 -->\r\n",
       "<g id=\"edge4\" class=\"edge\"><title>0&#45;&gt;4</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M188.585,-247.295C193.156,-232.741 198.54,-215.595 203.322,-200.369\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"205.712,-200.937 205.472,-193.524 201.037,-199.469 205.712,-200.937\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"201.5\" y=\"-216.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">r</text>\r\n",
       "</g>\r\n",
       "<!-- 2 -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>2</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"36\" cy=\"-36\" rx=\"36\" ry=\"36\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"36\" y=\"-42\" font-family=\"Times New Roman,serif\" font-size=\"20.00\">2</text>\r\n",
       "<text text-anchor=\"middle\" x=\"36\" y=\"-20\" font-family=\"Times New Roman,serif\" font-size=\"20.00\">(2,3)</text>\r\n",
       "</g>\r\n",
       "<!-- 1&#45;&gt;2 -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>1&#45;&gt;2</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M104.899,-129.631C92.0156,-112.31 75.4505,-90.039 61.7918,-71.6756\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"63.4242,-69.7651 57.2806,-65.6106 59.4925,-72.6895 63.4242,-69.7651\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"89\" y=\"-93.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">l</text>\r\n",
       "</g>\r\n",
       "<!-- 3 -->\r\n",
       "<g id=\"node4\" class=\"node\"><title>3</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"126\" cy=\"-36\" rx=\"36\" ry=\"36\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-42\" font-family=\"Times New Roman,serif\" font-size=\"20.00\">3</text>\r\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-20\" font-family=\"Times New Roman,serif\" font-size=\"20.00\">(5,7)</text>\r\n",
       "</g>\r\n",
       "<!-- 1&#45;&gt;3 -->\r\n",
       "<g id=\"edge3\" class=\"edge\"><title>1&#45;&gt;3</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126,-122.677C126,-109.133 126,-93.5409 126,-79.4013\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"128.45,-79.1582 126,-72.1582 123.55,-79.1582 128.45,-79.1582\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"128.5\" y=\"-93.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">r</text>\r\n",
       "</g>\r\n",
       "<!-- 5 -->\r\n",
       "<g id=\"node6\" class=\"node\"><title>5</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"216\" cy=\"-36\" rx=\"36\" ry=\"36\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"216\" y=\"-42\" font-family=\"Times New Roman,serif\" font-size=\"20.00\">5</text>\r\n",
       "<text text-anchor=\"middle\" x=\"216\" y=\"-20\" font-family=\"Times New Roman,serif\" font-size=\"20.00\">(7,2)</text>\r\n",
       "</g>\r\n",
       "<!-- 4&#45;&gt;5 -->\r\n",
       "<g id=\"edge5\" class=\"edge\"><title>4&#45;&gt;5</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M216,-122.677C216,-109.133 216,-93.5409 216,-79.4013\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"218.45,-79.1582 216,-72.1582 213.55,-79.1582 218.45,-79.1582\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"218\" y=\"-93.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">l</text>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x287a7259940>"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# point_list = [[2,3],[5,7],[9,6],[4,5],[6,4],[7,2]]\n",
    "point_list1 = [(2,3),(5,7),(9,6),(4,5),(6,4),(7,2)]\n",
    "tree = kdtree(point_list1)\n",
    "print(tree)\n",
    "create_graph(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "max_int = 10000000\n",
    "min_int = -max_int - 1\n",
    "max_float = float('inf')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_val_range(point_list):\n",
    "    min_val = max_int\n",
    "    max_val = -max_int - 1\n",
    "    for point in point_list:\n",
    "        min_v = min(point)\n",
    "        if min_v < min_val:\n",
    "            min_val = min_v\n",
    "        max_v = max(point)\n",
    "        if max_v > max_val:\n",
    "            max_val = max_v\n",
    "    return (min_val, max_val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "min_val, max_val=get_val_range(point_list1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAdoAAAHiCAYAAABPzQ1vAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAABDbklEQVR4nO3dfXBe6V3m+e8t2ZYldQsh3GpHUWSNSqPY8ptsmaTZQNMkdMiEFGzIDtVBIbAJaGY2y6ZhqmZhu3bD7uLhpWBIatndwUOYYYm2U0wIBRWgK6E63RkydLosW36VI7xCVtSKo/YIo27LlmTp3j/0ErVt+Uh6nqNzzuXrU+WyLT86+l0+v6Nbz7nPOXeIMWJmZmbpqMi6ADMzM2UeaM3MzFLkgdbMzCxFHmjNzMxS5IHWzMwsRR5ozczMUuSB1szMLEUeaM0yEEIYCSH84Kq/PxVC+PsQwveHEFpDCDGE8PrSr2+FEL4QQnhyjW21rHrt60ufe2PV379v65KZ2Z080JplLITwU8D/CfxwjPHFVf9UH2N8CDgMfAn4kxDCT9/5+THG0RjjQ8u/lj58eNXH/tOqr7UtvSRmdi8eaM0yFELoBX4L+KEY43++12tijFdjjJ8Cfhn49RDCuo/bEMJPhxC+GkL47RDCJPDLIYSqEMJvhhBGl94t/9sQQvWqz3lfCGEghHA9hPCfQwiHSktp9mDzQGuWnX8B/O/Au2KMJ9fx+s8DjcBbN/h13g4ML33uceDXgQ6gC2gH3gz8LwAhhKPA7wP/DPgu4HeBPwshVG3wa5rZEg+0Ztl5EngJOLfO148v/d6wwa8zHmP8P2KMt4FbwM8CPx9jnIwxvgb8a+Cppdf+LPC7McavxRjnY4x/AMwAj23wa5rZEg+0Ztn55yy+s/y9EEJYx+vfvPT75Aa/zjdW/fkRoAboXzo1fB14bunjAHuAf7n8b0v//hagaYNf08yWeKA1y84E8C7g+4D/ax2vf//S53x9g19n9RJd14CbwP4YY/3Sr+9YdRHVN4Djq/6tPsZYE2N8doNf08yWeKA1y1CMcRx4J/CeEMJv3+s1IYRHQwj/PfAJ4JdijAslfL0F4N8Bvx1CaFza/ptDCD+09JJ/B/zzEMLbw6LaEMIPhxAe3uzXNHvQeaA1y1iM8RssDrb/TQjhV1f90/UQwg0W53DfC/zTGOPvl+FL/o/AZeClEMIU8FcsXWC1dFHWzwK/A/z90ut+ugxf0+yBFbzwu5mZWXr8jtbMzCxFHmjNzMxS5IHWzMwsRR5ozczMUuSB1szMLEWprOTR0NAQ29ra0tj0lpmbm2P79u1Zl1EyhRwKGejv//afu7uzq6MUqzNAcXMg0lNo5FDIANDf338txvjIvf4tldt7Ojs748WLF8u+3a108uRJjh07lnUZJVPIoZCB1U9YLOotdXc+JbKoORDpKTRyKGQACCH0xxjvGcSnjs3MzFKUyjvaY8eOxZMn17PqV34tLCxQUVH8n0MUcihk8DvafJHoKTRyKGSADN7RzszMpLHZLTU8PJx1CWWhkEMhg+WLSk8p5FDIkCSVgXZ+fj6NzW6p69evZ11CWSjkUMhg+aLSUwo5FDIkKf77dTMzsxxLZaCtqqpKY7NbqqOjI+sSykIhh0IGyxeVnlLIoZAhSSoD7cLCppfLzI3p6emsSygLhRwKGSxfVHpKIYdChiSpDLRzc3NpbHZLjY2NZV1CWSjkUMhg+aLSUwo5FDIk8RytmZlZilIZaBUep9XU1JR1CWWhkEMhg+WLSk8p5FDIkCSVgbaysjKNzW6purq6rEsoC4UcChksX1R6SiGHQoYkqQy0t27dSmOzW+rSpUtZl1AWCjkUMli+qPSUQg6FDEk8R2tmZpaiVAZahedWqpzOUMihkMHyRaWnFHIoZEjiRQXMtoIXFTCTtuWLCijcgNx/5yLXBaWQQyGD5YtKTynkUMiQpPjneFOSxjv9LCjkUMhg+aLSUwo5FDIk8UC7hnDnabKCUsihkMHyRaWnFHIoZEjiOVqzreA5WjNpWz5Hq3Af7dDQUNYllIVCDoUMli8qPaWQQyFDEq/es4apqamsSygLhRwKGSxfVHpKIYdChiSeozUzM0tRKgPtzp0709jsltq7d2/WJZSFQg6FDJYvKj2lkEMhQ5JUBtr5+fk0NrulVE5nKORQyGD5otJTCjkUMiTxwu9rGB8fz7qEslDIoZDB8kWlpxRyKGRI4jlaMzOzFHnh9zU0NzdnXUJZKORQyGD5otJTCjkUMiTx6j1rqKmpybqEslDIoZDB8kWlpxRyKGRIksqIODMzk8Zmt5TKTdQKORQyWL6o9JRCDoUMSYr/1tPMzCzHUhloKysr09jslqqvr8+6hLJQyKGQwfJFpacUcihkSOJFBdawsLAgMdeskEMhgxcVyBeJnkIjh0IG8MLvm3Lq1KmsSygLhRwKGSxfVHpKIYdChiTF/zHCzMwsxzzQrkFhnhk0cihksHxR6SmFHAoZkniO1mwreI7WTJoXft+EwcHBrEsoC4UcChksX1R6SiGHQoYkXvh9DTdu3Mi6hLJQyKGQwfJFpacUcihkSOI5WjMzsxR54fc1dHZ2Zl1CWSjkUMhg+aLSUwo5FDIkSWWgvX37dhqb3VKTk5NZl1AWCjkUMli+qPSUQg6FDEk80K7h6tWrWZdQFgo5FDJYvqj0lEIOhQxJPEdrZmaWonUNtCGEj4cQzocQLoQQnk56/Y4dO0ouLGstLS1Zl1AWCjkUMli+qPSUQg6FDEkSB9oQwgHgZ4G3AYeB94UQ/nHC55Snugwp/LAAGjkUMli+qPSUQg6FDEnW8452H/BSjHE6xngbeBF4//0+QWHh98uXL2ddQlko5FDIYPmi0lMKORQyJNm2jtecB46HEL4LuAm8F7jr+YohhF6gF+DRRx9l+RGMzc3N1NTUMDQ0BCyuPdjW1rayYkNlZSVHjhxhcHBw5cblzs5OJicnVybJW1pa2LFjx8oOaWhooKWlhYGBAQC2b9/O4cOHuXDhAjdv3gTgwIEDTExMMDExAUBraysVFRUMDw8DsGvXLpqamjh79iwAVVVVHDx4kHPnzjEzM8P09DSzs7OMj49z7do1ANra2lhYWGBkZASAxsZGGhsbOX/+PADV1dXs37+fM2fOMDc3B0BXVxejo6MrV9a1t7czOzvL6OgoALt376ahoYGLFy8CUFtby759+zh9+jTz8/MAHD16lOHhYa5fvw5AR0cH09PTjI2NAdDU1ERdXR2XLl0CoK6ujo6ODvr7+5menqa/v5/u7m6GhoaYmpoCYO/evUxNTTE+Pp77/RRjXOmnO/cTwKFDh3K/n1Y/l205y+r9FGMkhJDr/XTnTXuTk5PrPp7ytp9mZmZW9sNGjqe87SegrN/3sthP09PTDA4OlvX7Xhb76X7W9azjEMJHgY8BrwMXgZsxxp9f6/UHDx6M586dS9xung0PD9PW1pZ1GSVTyKGQwc86zheJnkIjh0IGKMOzjmOMn44xHo0xPg5MAn97v9crnHNXmaBXyKGQwfJFpacUcihkSLLeq44bl35vAX4MePZ+r18+jVFky6dnik4hh0IGyxeVnlLIoZAhyXrmaAH+eGmOdg74WIzx71OsyczMTMa6BtoY4/dtZKMKt/csX2hQdAo5FDJYvqj0lEIOhQxJvPC72VbwxVBm0rZ84XeFOdoLFy5kXUJZKORQyGD5otJTCjkUMiRJZaBN413yVlP4YQE0cihksHxR6SmFHAoZknhRATMzsxSlMkfb3d0d+/v7y77drXTr1i2JBewVcihk8Bxtvkj0FBo5FDJABnO0y4/hKrLlR5gVnUIOhQyWLyo9pZBDIUMSL/y+BpWdr5BDIYPli0pPKeRQyJDEc7RmZmYpSmWgVXjWcWtra9YllIVCDoUMli8qPaWQQyFDEr+jXUNFhcZ/jUIOhQyWLyo9pZBDIUOSVBLOzs6msdkttbx+Y9Ep5FDIYPmi0lMKORQyJNH/UcLMzCxDqQy027atd1Gg/Nq1a1fWJZSFQg6FDJYvKj2lkEMhQ5JUBlqF1RiampqyLqEsFHIoZLB8UekphRwKGZJ4UYE1nD17NusSykIhh0IGyxeVnlLIoZAhiedozczMUpTKQKuw8HtVVVXWJZSFQg6FDJYvKj2lkEMhQxIv/G62FbyogJk0L/y+CefOncu6hLJQyKGQwfJFpacUcihkSOKF39cwMzOTdQlloZBDIYPli0pPKeRQyJDEF0OZmZmlyAu/r2F2dlZicQSFHAoZPEebLxI9hUYOhQzghd83ZXx8POsSykIhh0IGyxeVnlLIoZAhiRd+X8O1a9eyLqEsFHIoZLB8UekphRwKGZJ4jtbMzCxFXvh9DW1tbVmXUBYKORQyWL6o9JRCDoUMSfyOdg0LCwtZl1AWCjkUMli+qPSUQg6FDEm88PsaRkZGsi6hLBRyKGSwfFHpKYUcChmS+B2tmZlZirzw+xoaGxuzLqEsFHIoZLB8UekphRwKGZJ44fc1qOx8hRwKGSxfVHpKIYdChiReVGAN58+fz7qEslDIoZDB8kWlpxRyKGRI4jlaMzOzFHnh9zVUV1dnXUJZKORQyGD5otJTCjkUMiTxwu9mW8GLCphJ88Lvm3DmzJmsSygLhRwKGSxfVHpKIYdChiRe+H0NCisQgUYOhQyWLyo9pZBDIUMSXwxlZmaWIi/8vobbt29LPHhDIYdCBs/R5otET6GRQyEDlGGONoTw8yGECyGE8yGEZ0MIO+/3eoVnHY+OjmZdQlko5FDIYPmi0lMKORQyJEkcaEMIbwb+B+BYjPEAUAk8db/PmZ+fL091GZqcnMy6hLJQyKGQwfJFpacUcihkSLLeOdptQHUIYRtQA4ynV5KZmZmOxIE2xvgK8JvAKPBN4B9ijF+83+dUVVWVp7oMtbe3Z11CWSjkUMhg+aLSUwo5FDIkSZyBDiF8J/CjwD8CrgP/MYTwoRjjZ+54XS/QC9DU1MTyAyuam5upqalhaGgIgPr6etra2jh16hQAlZWVHDlyhMHBQW7cuAFAZ2cnk5OTXL16FYCWlhZ27NjB5cuXAWhoaKClpYWBgQFgcRGDw4cPc+HChZV7eA8cOMDExAQTExMAtLa2UlFRwfDwMAC7du2iqamJs2fPAos/HBw8eJBz584xMzPD7du3OXr0KOPj41y7dg2AtrY2FhYWVtZPbGxspLGxceVZndXV1ezfv58zZ86sXLLe1dXF6OjoyumR9vZ2ZmdnV+Yldu/eTUNDAxcvXgSgtraWffv2cfr06ZVT8EePHmV4eJjr168D0NHRwfT0NGNjYyz/f9fV1XHp0iUA6urq6OjooL+/n7m5ObZv3053dzdDQ0NMTU0BsHfvXqamphgfH8/9flq9zTv3E8ChQ4dyv59WXyGxfGys3k8xRkIIud5Pd16YMTk5ue7jKW/7aXR0dCX/Ro6nvO2nN73pTWX9vpfFfrp9+zbf8R3fUdbve1nsp/tJvOo4hPBPgffEGD+69PcPA4/FGP+7tT6ns7MzLjd6UZ08eZJjx+55AVmhKORQyOCrjvNFoqfQyKGQAUq/6ngUeCyEUBMWH2L8LmCwnAWamZmpWs8c7deAzwGngHNLn3Pifp+jcE/U7t27sy6hLBRyKGSwfFHpKYUcChmSrGtEjDF+AvjEujcqMNA2NDRkXUJZKORQyGD5otJTCjkUMiRJ5RGMt27dSmOzW6roc8zLFHIoZLB8UekphRwKGZL4WcdmZmYpSmWgrago/vhdW1ubdQlloZBDIYPli0pPKeRQyJDEC7+bbQXf3mMmbcsXfp+enk5js1vq9OnTWZdQFgo5FDJYvqj0lEIOhQxJin+ONyUKCyOARg6FDJYvKj2lkEMhQxIPtGZmZinyHO0aFhYWJC7qUsihkMFztPki0VNo5FDIABnM0S4/nLrIlh/CXXQKORQyWL6o9JRCDoUMSVIZaBXOuS+vGFF0CjkUMli+qPSUQg6FDEmK/37dzMwsx1IZaBUWfu/o6Mi6hLJQyKGQwfJFpacUcihkSJLKQLuwsJDGZreUwr3AoJFDIYPli0pPKeRQyJAklYF2bm4ujc1uqbGxsaxLKAuFHAoZLF9Uekohh0KGJJ6jNTMzS1EqA+327dvT2OyWampqyrqEslDIoZDB8kWlpxRyKGRIkspAW1lZmcZmt1RdXV3WJZSFQg6FDJYvKj2lkEMhQxIv/L6GS5cuZV1CWSjkUMhg+aLSUwo5FDIk8RytmZlZirzw+xpUTmco5FDIYPmi0lMKORQyJPGiAmZbwYsKmEnzwu+b0N/fn3UJZaGQQyGD5YtKTynkUMiQpPjneFOSxjv9LCjkUMhg+aLSUwo5FDIk8UC7hnDnabKCUsihkMHyRaWnFHIoZEjiOVqzreA5WjNpWz5Hq3Af7dDQUNYllIVCDoUMli8qPaWQQyFDEq/es4apqamsSygLhRwKGSxfVHpKIYdChiSeozUzM0tRKgPtzp0709jsltq7d2/WJZSFQg6FDOtx69Yt3va2t3H48GH279/PJz7xiaxLkqXSUwo5FDIkSWWgnZ+fT2OzW0rldIZCDoUM61FVVcXzzz/PmTNnGBgY4LnnnuOll17KuixJKj2lkEMhQxIv/L6G8fHxrEsoC4UcChnWI4TAQw89BCweQ3Nzcw/ErQ9ZUOkphRwKGZJ4jtYsR+bn5+nq6qKxsZEnn3ySt7/97VmXZGYl8sLva2hubs66hLJQyKGQYb0qKysZGBhgbGyMl19+mfPnz2ddkiSVnlLIoZAhiVfvWUNNTU3WJZSFQg6FDBtVX1/PE088wXPPPZd1KZJUekohh0KGJKmMiDMzM2lsdkup3EStkEMhw3q8+uqrXL9+HYCbN2/yV3/1Vw/EFZlZUOkphRwKGZJsy7oAM1v0zW9+k5/6qZ9ifn6ehYUFfvzHf5z3ve99WZdlZiVKZaCtrKxMY7Nbqr6+PusSykIhh0KG9Th06BCnT5/OuowHgkpPKeRQyJDEiwqsYWFhQWKuWSGHQgYvKpAvEj2FRg6FDOCF3zfl1KlTWZdQFgo5FDJYvqj0lEIOhQxJEgfaEMJbQwgDq35NhRCe3oLazMzMCi9xoI0xfj3G2BVj7AK6gWngT9IuLGsK88ygkaPoGfr6+mhl8WBrXfq7ZavoPbVMIYdChiQbmqMNIbwb+ESM8R33e53CHK1ZOfT19dHb2/uG6ZSamhpOnDhBT09PhpVtgtAcrVm5lXOO9ing2aQXKSz8Pjg4mHUJZaGQo8gZnnnmmbuuWZienuaZZ57JqCKDYvfUago5FDIkWfc72hDCDmAc2B9j/NY9/r0X6AV49NFHu7/whS8Ai4/XqqmpWbkpub6+nra2tpUJ8MrKSo4cOcLg4CA3btwAoLOzk8nJSa5evQpAS0sLO3bs4PLlywA0NDTQ0tLCwMAAsPjIx8OHD3PhwgVu3rwJwIEDB5iYmGBiYgKA1tZWKioqGB4eBmDXrl00NTVx9uxZYHHllIMHD3Lu3DlmZmaYnp7mscceY3x8nGvXrgHQ1tbGwsICIyMjADQ2NtLY2LjymLzq6mr279/PmTNnVhZW6OrqYnR0lMnJSQDa29uZnZ1ldHQUgN27d9PQ0MDFixcBqK2tZd++fZw+fXplFaSjR48yPDy88jCDjo4OpqenGRsbA6CpqYm6ujouXboEQF1dHR0dHfT393Pjxg1qa2vp7u5maGhoZaWMvXv3MjU1tfJA7zzvp1dffXXl4fp37idYvC0mr/upvr6eex1jIQQuXbq0sp9ijIQQcr2fdlZXvyHD5H/5L+s+nvK2n/7mb/6Gqqqqlf203uMpb/tpbm6O6urqsn3fy2I/TU9P88gjj5T1+14W++k7v/M713xHu5GB9keBj8UY35302s7Ozrjc6EV18uRJjh275/9ZoSjkKHKG1tZWrly5ctfH9+zZs/KNqzCETh0XuadWU8ihkAHKd+r4g6zjtDFoLPze2dmZdQlloZCjyBmOHz9+17Nca2pqOH78eEYVGRS7p1ZTyKGQIcm6BtoQQg3wJPD59bz+9u3bpdSUC8unPIpOIUeRM/T09HDixAn2AAHYA8W8EEpMkXtqNYUcChmSrGugjTFOxxi/K8b4D+t5vcJAu3z+vegUchQ9Q09PDyPAAjCy9HfLVtF7aplCDoUMSYr/3CszM7McS2Wg3bFjRxqb3VItLS1Zl1AWCjkUMli+qPSUQg6FDElSGWjDnVcnFpDCDwugkUMhg+WLSk8p5FDIkMQLv69h+d61olPIoZDB8kWlpxRyKGRI4jlaMzOzFKUy0Co8JLqhoSHrEspCIYdCBssXlZ5SyKGQIYkvhlqDygS9Qg6FDJYvKj2lkEMhQ5JUBtrl524W2fLzRItOIYdCBssXlZ5SyKGQIYnnaM3MzFLk23vWsH379qxLKAuFHAoZLF9Uekohh0KGJBta+H29vPC72R1W//BZ1FVvhFbvMSu3ci78vi4Kc7QXLlzIuoSyUMihkMHyRaWnFHIoZEiSykCbxrvkrabwwwJo5FDIYPmi0lMKORQyJPHFUGZmZilKZY62u7s79vf3l327W+nWrVsSC9gr5FDI4DnafJHoKTRyKGSADOZo5+bm0tjslpqYmMi6hLJQyKGQwfJFpacUcihkSJLKQKuw8LvKzlfIoZDB8kWlpxRyKGRI4jlaMzOzFPlZx2tobW3NuoSyUMihkMHyRaWnFHIoZEjid7RrqKjQ+K9RyKGQwfJFpacUcihkSJJKwtnZ2TQ2u6WGh4ezLqEsFHIoZLB8UekphRwKGZLo/yhhZmaWoVQG2m3btqWx2S21a9eurEsoC4UcChksX1R6SiGHQoYkqQy0CqsxNDU1ZV1CWSjkUMhg+aLSUwo5FDIk8aICazh79mzWJZSFQg6FDJYvKj2lkEMhQxLP0ZqZmaXIC7+voaqqKusSykIhh0IGyxeVnlLIoZAhiRd+N9sKXlTATJoXft+Ec+fOZV1CWSjkUMhg+aLSUwo51pthfn6eI0eO8L73vS/lisrPC7+vYWZmJusSykIhh0IGyxeVnlLIsd4Mn/rUp9i3b1/K1aTDF0OZmVmujY2N8ed//uf8zM/8TNalbEoqA211dXUam91Shw4dyrqEslDIoZDB8kWlpxRyrCfD008/zW/8xm8U9rnIXvh9DePj41mXUBYKORQyWL6o9JRCjqQMX/jCF2hsbKS7u3uLKio/L/y+hmvXrmVdQlko5FDIYPmi0lMKOZIyfPWrX+XP/uzPaG1t5amnnuL555/nQx/60BZVVx7FfB9uZmYPhF/91V9lbGyMkZERPvvZz/LOd76Tz3zmM1mXtSFe+H0NbW1tWZdQFgo5FDJYvqj0lEIOhQxJir/MTkoWFhayLqEsFHIoZLB8UekphRwbyfDEE0/wxBNPpFdMSrzw+xpGRkayLqEsFHIoZLB8UekphRwKGZJ4jtbMzCxF6xpoQwj1IYTPhRAuhRAGQwjfc7/XKyz83tjYmHUJZaGQQyGD5YtKTynkUMiQZL3vaD8FPBdj3AscBgbv92KFhd9Vdr5CDoUMli8qPVXkHH19fbS2tq786uvry7qk1CS+9Qwh1AGPAz8NEGOcBe47CauwqMD58+c5duyeCzEUikIOhQwKnua3GaDr2x94IqtKSvfaa3M8/PDOrMsoWVFzfOtbfQwN9bKwMA3AlStX+PCHe/mVX4FHH+3JuLryW8853jbgVeDfhxAOA/3Ax2OMN1KtzMxyZYAuXlw9ur6YWSkliXx7ub9A0RdAeTjrAjbpGWD6DR9ZWJjm0qVnuHTpwRxotwFHgZ+LMX4thPAp4BeB/3n1i0IIvUAvwO7du1lej7a5uZmamhqGhoYAqK+vp62tjVOnTgFQWVnJkSNHGBwc5MaNxbG7s7OTyclJrl69CkBLSws7duzg8uXLADQ0NNDS0sLAwACweKr68OHDXLhwYeXd9IEDB5iYmGBiYgKA1tZWKioqGB4eBmDXrl00NTVx9uxZYHHx4YMHD3Lu3DlmZma4desWs7OzjI+Przy5pK2tjYWFhZWr5BobG2lsbOT8+fPA4jOe9+/fz5kzZ1YeQ9nV1cXo6CiTk5MAtLe3Mzs7y+joKMv/Vw0NDVy8eBGA2tpa9u3bx+nTp5mfnwfg6NGjDA8Pc/36dQA6OjqYnp5mbGwMgKamJurq6rh06RIAdXV1dHR00N/fz61bt+jv76e7u5uhoSGmpqYA2Lt3L1NTUyuPP8vzfqqqqlrppzv3Eyw+KzXv+2n1+/HlLKv3U4yREEKu95NZ+Yxu8OPFlrjwewhhN/BSjLF16e/fB/xijPGH1/ocL/xudgeBhd+fDp9846nj738iq1JK8sKL394XT3x/MfdF0b30UiszM1fu+nhV1R4ee2xk6wsqgxdfXHvh98R3tDHGqyGEb4QQ3hpj/DrwLuDi/T5HYY72zJkzHD58OOsySqaQQyGDgk/y82/8wAsFHaRW/czzwguZVVEWRT02+vqO09vby/T0t08f19TUcOLEcXoKeuZ49c/Sd1rvVcc/B/SFEM4CXcC/vt+LFRZ+V1iBCDRyKGQwS0NRj42enh5OnDjBnj17CCGwZ88eTpw4QU9RR9kE67rhNcY4APiyTzMzK4uenh56eno4efKk/F0FiXO0m9Hd3R37+/vLvt2tdPv2bYkHbyjkUMigMEd717kxhRxFzbBE4dhQyAAQwtpztH7W8RqWrzYtOoUcChnM0qBwbChkSJLKQLt8u0ORLd/mUXQKORQymKVB4dhQyJDEiwqYmZmlKJWBtqqqKo3Nbqn29vasSygLhRwKGczSoHBsKGRIkspAq3B7j8I8M2jkUMhglgaFY0MhQxJfDLUGlQl6hRwKGczSoHBsKGRI4jlaMzOzFKUy0CrcE7V79+6sSygLhRwKGczSoHBsKGRI4oF2DQ0NDVmXUBYKORQymKVB4dhQyJAklYH21q1baWx2Sy0vh1Z0CjkUMpilQeHYUMiQxHO0ZmZmKUploK2oKP74XVtbm3UJZaGQQyGDWRoUjg2FDElSWVTAC7+b3UHhQfZeVMBsTVu+qMDqxXyL6vTp01mXUBYKORQymKVB4dhQyJCk+Od4U6KwMAJo5FDIYJYGhWNDIUMSD7RmZmYp8hztGhYWFiQu6lLIoZBBYl7Qc7S5o3BsKGSADOZoZ2Zm0tjslhoeHs66hLJQyKGQwSwNCseGQoYkXvh9DdevX8+6hLJQyKGQwSwNCseGQoYkxX+/bmZmlmNe+H0NHR0dWZdQFgo5FDKYpUHh2FDIkCSVgXZhYSGNzW4phXuBQSOHQgazNCgcGwoZkqQy0M7NzaWx2S01NjaWdQlloZBDIYNZGhSODYUMSTxHa2ZmlqJUBtrt27ensdkt1dTUlHUJZaGQQyGDWRoUjg2FDElSGWgrKyvT2OyWqqury7qEslDIoZDBLA0Kx4ZChiRe+H0Nly5dyrqEslDIoZDBLA0Kx4ZChiSeozUzM0uRF35fg8rpDIUc68nwkY98hMbGRg4cOLAFFZnlw4NyfBedFxUwCV/5yld46KGH+PCHP8z58+ezLuduCg+y96ICZmvywu+b0N/fn3UJZaGQYz0ZHn/8cRoaGragGrP8eFCO76Ir/jnelKTxTj8LCjkUMpilQeHYUMiQxAPtGsKdp8kKSiGHQgazNCgcGwoZkqQy0NbU1KSx2S3V3d2ddQlloZBDIYNZGhSODYUMSXwf7RqGhoayLqEsFHIoZDBLg8KxoZAhiVfvWcPU1FTWJZSFQo71ZPjgBz/I93zP9/D1r3+d5uZmPv3pT29BZWbZelCO76LblnUBZuXw7LPPZl2Cmdk9pfKOdufOnWlsdkvt3bs36xLKQiGHQgazNCgcGwoZkqQy0M7Pz6ex2S2lcjpDIYdCBrM0KBwbChmSrGugDSGMhBDOhRAGQgiJj3xSWPh9fHw86xLKQiGHQgazNCgcGwoZkmzkHe0PxBi71nrElFm59fX10draytve9jZaW1vp6+vLuiQzsw1L5WKo0dFqnngijS1vndnZQ+zYkXUVpStqjm99q4+hoV4WFhYf53nlyhU+/OFefuVX4NFHezKubuNeWPXn4h4bX175UxcDfDK7QmxJc3Nz1iWUTCFDknUtKhBC+Dvg74EI/G6M8cT9X38sQnEXFYh8+0klAf3Hg+VTK3DlHh/fA4xsaSXloNZT388LvBCfyLqMzRFaVGBqaqrwq98oZID7Lyqw3ne074gxjocQGoEvhRAuxRi/cscX6QV6F/+m/6QPS9voBj9uW21ycpLh4WEAdu3aRVNTE2fPngWgqqqKgwcPcu7cOWZmZgA4dOgQ4+PjXLt2DYC2tjYWFhYYGRkBoLGxkcbGxpXVl6qrq9m/fz9nzpxZue6jq6uL0dFRJicnAWhvb2d2dpbR0cW+2L17Nw0NDVy8eBGA2tpa9u3bx+nTp1cu0lz9nfDkyZN0dHQwPT3N2NgYAE1NTdTV1a0sSF5XV0dHRwf9/f3EGAkh0N3dzdDQ0MqFPHv37mVqamplvrG5uZmampqVhzHU19fT1tbGqVOnAKisrOTIkSMMDg5y48YNADo7O5mcnOTq1asAtLS0sGPHDi5fvgxAQ0MDLS0tDAwMALB9+3bm5uaorq7m5s2bABw4cICJiQkmJiYAaG1tpaKiItf7aXp6mkceeeSu/XT06FGGh4e5fv06QO730/1seJm8EMIvA6/HGH9zrdfU1h6N3/3dpza03Tx54cVv/8T7xPcX+yfe1157jYcffjjrMjbspZdamZm5+x1tVdUeHntsZOsLKpFET734wsofuxjgk/HpzEopidA72pMnT3LsWLEvm1HIACW+ow0h1AIVMcbXlv78buB/u9/ntLXN8cILmyk1J1Ydh4XOAVy+/C3a24s30Pb1Hae3t/cNSy7W1NRw4sRxeoo3RQtELl++THt7+xvmawsl/MAdH3g6iypslfr6+qxLKJlChiTruer4UeCvQwhngJeBP48xPne/T6iqqipHbVYGbW1tWZewKT09PZw4cYI9e/YQQmDPnj2cOHGCnmKOskBx94Xll0JPKWRIkjjQxhiHY4yHl37tjzEeT/ochYXfVSzPNRRRT08PIyMjvPzyy4yMjBR6kIVi7wvLJ4WeUsiQxOvRmpmZpcgDrbjKysqsSyiZQgbQyWH5odBTChmSbPiq4/U4duxYPHmyuPfRKl2VaFY2q48LKO6x4ePbUnC/q4698Lu4wcHBrEsomUIG0Mlh+aHQUwoZknjhd3HLN1kXmUIG0Mlh+aHQUwoZkniO1szMLEVe+F1cZ2dn1iWUTCED6OSw/FDoKYUMSVIZaG/fvp3GZm0Tlp81WmQKGUAnh+WHQk8pZEjigVbc8oOvi0whA+jksPxQ6CmFDEk8R2tmZpaiVAbapCWDbOu0tLRkXULJFDKATg7LD4WeUsiQJJWBNtx5Y7tlRuGHHoUMoJPD8kOhpxQyJElloF1eQNiyt7xodJEpZACdHJYfCj2lkCGJ52jNzMxSlMpA+yA8JLooGhoasi6hZAoZQCeH5YdCTylkSOKLocQpXGigkAF0clh+KPSUQoYkqQy0N2/eTGOztgkDAwNZl1AyhQygk8PyQ6GnFDIk8RytmZlZinx7j7jt27dnXULJFDKATg7LD4WeUsiQxAu/34sXhja7mxd+N1vTli/87jna/Lhw4ULWJZRMIQPo5LD8UOgphQxJUhlo03iXbJuj8EOPQgbQyWH5odBTChmS+GIoMzOzFKUyR9vd3R37+/vLvt0tIzSHc+vWLXbu3Jl1GSVRyAACOTxHmzuF7yk0MkAGc7Rzc3NpbNY2YWJiIusSSqaQAXRyWH4o9JRChiRe+F2cQhMrZACdHJYfCj2lkCGJ52jNzMxS5Gcdi2ttbc26hJIpZACdHJYfCj2lkCGJ39GKq6go/i5WyAA6Odbjueee461vfSvt7e382q/9WtblyFLoKYUMSVJJODs7m8ZmbROGh4ezLqFkChlAJ0eS+fl5Pvaxj/GXf/mXXLx4kWeffZaLFy9mXZYkhZ5SyJBE/0cJM9tSL7/8Mu3t7bS1tbFjxw6eeuop/vRP/zTrsswyk8pAu23btjQ2a5uwa9eurEsomUIG0MmR5JVXXuEtb3nLyt+bm5t55ZVXMqxIl0JPKWRIkspA+yCsxlAUTU1NWZdQMoUMoJMjyb0eguMVvdKh0FMKGZJ4UQFxZ8+ezbqEkilkAJ0cSZqbm/nGN76x8vexsbEH4ptpFhR6SiFDEs/RmllZffd3fzd/+7d/y9/93d8xOzvLZz/7WX7kR34k67LMMpPKZKpPE+VHVVVV1iWUTCED6ORIsm3bNn7nd36HH/qhH2J+fp6PfOQj7N+/P+uyJCn0lEKGJF74/V6EHjpuVjZeVMBsTV74/QF27ty5rEsomUIG0Mlh+aHQUwoZknjhd3EzMzNZl1AyhQygk8PyQ6GnFDIkWfdAG0KoDCGcDiF8Ic2CzMzMlGzkHe3HgcH1vLC6unpz1VjZHTp0KOsSSqaQAYqfow9oZfGbRivQ19eXZTlG8XsKNDIkWddAG0JoBn4Y+L31vN4Lv+fH+Ph41iWUTCEDFDtHX18fvcAVIC793tvb68E2Y0XuqWUKGZKs9x3tJ4F/BSys58Ve+D0/rl27lnUJJVPIAMXO8cwzzzB9x8emp6d55plnMqnHFhW5p5YpZEiSeB9tCOF9wESMsT+E8MR9XtcL9AI8+uijLN/e09zcTE1NDUNDQwDU19fT1tbGqVOnAKisrOTIkSMMDg5y48YNADo7O5mcnOTq1asAtLS0sGPHDi5fvgxAQ0MDLS0tDAwMAIuPfDx8+DAXLlxYueL5wIEDTExMMDExASyueVhRUbGyUsSuXbtoampaeSpJVVUVBw8e5Ny5cxxclWtkZGSlEdra2lhYWGBkZASAxsZGGhsbOX/+PLB4ynz//v2cOXNm5V19V1cXo6OjTE5OAtDe3s7s7Cyjo6MA7N69m4aGhpXVTWpra9m3bx+nT59mfn4egKNHjzI8PMz169cB6OjoYHp6mrGxMWDxEWZ1dXVcunQJgLq6Ojo6Oujv72d6epr+/n66u7sZGhpiamoKgL179zI1NbXy02Se91OMcaWfVu+n5YsoDh06xPj4eO7309zcHK+//vo991OMkRBCbvfT8v/DnUZHRzl58uR9j6e87afV91+cPHlyQ8dT3vYTULbve1ntp+npaQYHB8v6fS+L/XQ/iffRhhB+FfhJ4DawE6gDPh9j/NBan9PV1RWXm6GQhO6zm5ycpKGhIesySqKQAYqdo7W1lStXrtz18T179qx8Ay4MH9+5opABSryPNsb4SzHG5hhjK/AU8Pz9BlnLl4WFdZ3tzzWFDFDsHMePH6fmjo/V1NRw/PjxTOqxRUXuqWUKGZJ44XdxhXu3cQ8KGaDYOXp6ejgB7AHC0u8nTpygp6cn28IecEXuqWUKGZJs6FnHMcYXgBdSqcTMcq1n6de3P+BB1mw9vPC7uMbGxqxLKJlCBtDJYfmh0FMKGZJ44XdxCk2skAF0clh+KPSUQoYkXlRA3PIl+EWmkAF0clh+KPSUQoYkXvjdzMwsRakMtF74PT8UnjutkAF0clh+KPSUQoYkXvj9XoRuaDcrGy/8brYmL/z+ADtz5kzWJZRMIQPo5LD8UOgphQxJvPC7OIWVlBQygE4Oyw+FnlLIkMQXQ5mZmaUolTna7u7u2N/fX/btbhmhOZzbt28X/gEiChlAIIfnaHOn8D2FRgbIYI7WzzrOj7WWNysShQygk8PyQ6GnFDIkSWWgXV5P0LK3vB5kkSlkAJ0clh8KPaWQIYnnaM3MzFKUykBbVVWVxmZtE9rb27MuoWQKGUAnh+WHQk8pZEji23vEKcyXK2QAnRyWHwo9pZAhiS+GEqdwoYFCBtDJYfmh0FMKGZJ4jtbMzCxFXvhd3O7du7MuoWQKGUAnh+WHQk8pZEjigVZcQ0ND1iWUTCED6OSw/FDoKYUMSVIZaG/dupXGZm0TLl68mHUJJVPIADo5LD8UekohQxLP0ZqZmaUolYG2osLjd17U1tZmXULJFDKATg7LD4WeUsiQxAu/34vQQ8fNysaLCpitacsXFZienk5js7YJp0+fzrqEkilkAJ0clh8KPaWQIYnP8YpTWOBBIQPo5LD8UOgphQxJPNCamZmlyHO09yI0h7OwsFD4i9MUMoBADs/R5k7hewqNDJDBHO3MzEwam7VNGB4ezrqEkilkAJ0clh8KPaWQIYkXft+kb3zjG/zAD/wA+/btY//+/XzqU5/KuqR7un79etYllEwhA+jksPxQ6CmFDEn8rMRN2rZtG7/1W7/F0aNHee211+ju7ubJJ5+ks7Mz69LMzCxHvPD7Jr3pTW/i6NGjADz88MPs27ePV155JeOq7tbR0ZF1CSVTyAA6OSw/FHpKIUOSVAbahYWFNDabWyMjI5w+fZq3v/3tWZdyF4V7mhUygE4Oyw+FnlLIkCSVgXZubi6NzebS66+/zgc+8AE++clPUldXl3U5dxkbG8u6hJIpZACdHJYfCj2lkCFJ8a+pztDc3Bwf+MAH6Onp4cd+7MeyLsfMzHIolYF2+/btaWw2V2KMfPSjH2Xfvn38wi/8QtblrKmpqSnrEkqmkAF0clh+KPSUQoYkqQy0lZWVaWw2V7761a/yh3/4hzz//PN0dXXR1dXFX/zFX2Rd1l3yeDp7oxQygE4Oyw+FnlLIkMQLv2/S937v9xJj5OzZswwMDDAwMMB73/verMu6y6VLl7IuoWQKGUAnh+WHQk8pZEjiOVozM7MUeeF3cQqnZRQygE4Oyw+FnlLIkCRxUYEQwk7gK0AVi0+S+lyM8RP3+xwvKmAmyIsKmK2p1EUFZoB3xhgPA13Ae0IIj93vE4p8A3JfXx+tLP7HtC79vcj6+/uzLqFkChlAJ4flh0JPKWRIkvis47j4lvf1pb9uX/ol+WNgX18fvb29LP+YcAXo7e0FoKenJ7O6SpHGMohbTSED6OSw/FDoKYUMSdY1mRpCqAwhDAATwJdijF9LtaqMPPPMM3e9G5+enuaZZ57JqKLShTtP9xWQQgbQyWH5odBTChmSrGv1nhjjPNAVQqgH/iSEcCDGeH71a0IIvUAvwJvf/GaW52ibm5upqalhaGgIgPr6etra2jh16hSweM/tkSNHGBwc5MaNGwB0dnYyOTnJ1atXAWhpaWHHjh1cvnwZgIaGBlpaWhgYGAAWH5Bx+PBhLly4wM2bNwE4cOAAExMTTExMANDa2kpFRcXK2oe7du2iqamJs2fPAosLIYyOjt4z/+joKCdPnqStrY2FhQVGRkYAaGxspLGxkfPnF/8rqqur2b9/P2fOnFl5DGVXVxejo6NMTk4C0N7ezuzs7MrX2r17Nw0NDVy8eBGA2tpa9u3bx+nTp1eWGzx69CjDw8Mry0l1dHQwPT298uiypqYm6urqVi6Tr6uro6Ojg/7+fmKM9Pf3093dzdDQEFNTUwDs3buXqakpxsfHc7+fDh48uNJPVVVVHDx4kHPnzq2se3zo0CHGx8e5du0aQK730+uvv77mfgoh5Ho/7eSNJicn73s85XU/rZ5EO3ny5IaPpzztp+7u7pK/7+VhPw0ODpb9+95W76f7SbwY6q5PCOETwI0Y42+u9ZoDBw7E5Z1QJK2trVy5cuWuj+/Zs2elyYpmaGio8KtjKGQAgRy+GCp3Ct9TaGSAEi+GCiE8svROlhBCNfCDwH3vMC7q6j3Hjx+npqbmDR+rqanh+PHjGVVUuuWf5IpMIQPo5LD8UOgphQxJ1nPq+E3AH4QQKlkcmP8oxviFdMvKxvIFT8986EOMAi3A8RMnCnshlJmZZW/Dp47X4+jRo3H5HHchCZ1aev3113nooYeyLqMkChlAIIdPHedO4XsKjQxQ+n20G7Y8mW3ZUzgto5ABdHJYfij0lEKGJF74Xdzy1XVFppABdHJYfij0lEKGJH4osZmZWYq88Lu45ubmrEsomUIG0Mlh+aHQUwoZknj1HnF33q5URAoZQCeH5YdCTylkSJLKiLj8hBHL3vITT4pMIQPo5LD8UOgphQxJ/NbTzMwsRakMtJWVlWls1jahvr4+6xJKppABdHJYfij0lEKGJKk8sMILv+fHwsJC4efMFTKAQA4/sCJ3Ct9TaGSADB5YUeSF39UU+gldSxQygE4Oyw+FnlLIkKT4P0aYmZnlmAdacQrz5QoZQCeH5YdCTylkSOI52nsRmsMxKxvP0ZqtacvnaG/dupXGZm0TBgcHsy6hZAoZQCeH5YdCTylkSJLKQFvUhd8V3bhxI+sSSqaQAXRyWH4o9JRChiSeozUzM0tRKgPtzp0709isbUJnZ2fWJZRMIQPo5LD8UOgphQxJUhlob9++ncZmbRMmJyezLqFkChlAJ4flh0JPKWRI4oFW3NWrV7MuoWQKGUAnh+WHQk8pZEjiOVozM7MUpTLQ7tixI43N2ia0tLRkXULJFDKATg7LD4WeUsiQJJWBNtx5Y7tlRuGHHoUMoJPD8kOhpxQyJPHC7+IuX76cdQklU8gAOjksPxR6SiFDEs/RmpmZpcgLv4traGjIuoSSKWQAnRyWHwo9pZAhiS+GEqdwoYFCBtDJYfmh0FMKGZKkMtDevHkzjc3aJgwMDGRdQskUMoBODssPhZ5SyJDEc7RmZmYp8u094rZv3551CSVTyAA6OSw/FHpKIUMSL/x+L14Y2uxuD9jC762trTz88MNUVlaybds2Cv09zVK35Qu/e442Py5cuJB1CSVTyAA6OR4kX/7ylxkYGMjtIKvQUwoZkqQy0KbxLtk2R+GHHoUMoJPD8kOhpxQyJPHFUGZm9xBC4N3vfjfd3d2cOHEi63KswLalsdHq6uo0NmubcODAgaxLKJlCBtDJ8aD46le/SlNTExMTEzz55JPs3buXxx9/POuy3kChpxQyJEnlHe3c3Fwam7VNmJiYyLqEkilkAJ0cD4qmpiYAGhsbef/738/LL7+ccUV3U+gphQxJvPC7OIUmVsgAOjkeBDdu3OC1115b+fMXv/jFXL7zUugphQxJUjl1bGZWZN/61rd4//vfDyy+cfiJn/gJ3vOe92RclRVVKgOtn3WcH62trVmXUDKFDKCT40HQ1tbGmTNnsi4jkUJPKWRI4quOxVVUFH8XK2QAnRyWHwo9pZAhSSoJZ2dn09isbcLw8HDWJZRMIQPo5LD8UOgphQxJEgfaEMJbQghfDiEMhhAuhBA+vhWFmZmVW19fH60sfuNrXfq7WdrWM0d7G/iXMcZTIYSHgf4QwpdijBfX3Og2X2OVF7t27cq6hJIpZACdHEXV19dHb28v00t/vwL09vYC0NPTk1ldpVDoKYUMSTa8qEAI4U+B34kxfmmt13R3d8f+/v5Sa8uO0KICs7Ozhb84TSEDCOQo+KICra2tXLly5a6P79mzh5GRka0vqAwK31NoZID7LyqwobeeIYRW4AjwtXv8Wy/QC/Doo4+uPIS7ubmZmpoahoaGAKivr6etrY1Tp04BUFlZyZEjRxgcHOTGjRsAdHZ2Mjk5ydWrVwFoaWlhx44dXL58GYCGhgZaWlpWFgzevn07hw8f5sKFCyvPzTxw4AATExMr92i1trZSUVGxMh+wa9cumpqaOHv2LABVVVUcPHiQc+fOcXBVrpGREa5duwYsXom4sLCwclA2NjbS2NjI+fPngcUnYu3fv58zZ86sPLSjq6uL0dFRJicnAWhvb2d2dpbR0VEAdu/eTUNDAxcvLp4gqK2tZd++fZw+fZr5+XkAjh49yvDwMNevXwego6OD6elpxsbGgMUb6+vq6rh06RIAdXV1dHR00N/fz40bN6itraW7u5uhoSGmpqYA2Lt3L1NTU4yPj+d+P7366qsrSy+u3k8zMzMAHDp0iPHx8dzvp7m5OQ4ePHjP/RRjJISQ6/20kzeanJxc1/GUl/20/Jo7jY6OcvXq1XUdT3nbT3Nzc1RXV5fl+15W+2l6eppHHnmkrN/3sthP97Pud7QhhIeAF4HjMcbP3++1nZ2dcbnRC0noHe3Jkyc5duyeP2QVhkIGEMjhd7S5U/ieQiMDlGGZvBDCduCPgb6kQXbp9Rur0FJTVVWVdQklU8gAOjmK6vjx49TU1LzhYzU1NRw/fjyjikqn0FMKGZIkvqMNi6PmHwCTMcan17NRL/xuJqjg72hh8YKoZz70IUaBFuD4Zz5T2AuhLF9KfUf7DuAngXeGEAaWfr33fp/wIKwvWBTnzp3LuoSSKWQAnRxF1tPTwwiwAIxQ3KuNlyn0lEKGJIkXQ8UY/xrY0LlgL/yeH8sXOBSZQgbQyWH5odBTChmS6D/7yszMLEMbvo92PXwfbX4o3KOmkAEEcgjM0QI+vnNGIQOU4arjjfLC7/mxfL9YkSlkAJ0clh8KPaWQIYkXfhe3fNN5kSlkAJ0clh8KPaWQIYnnaM3MzFKUykCrcL5dRVtbW9YllEwhA+jksPxQ6CmFDEn8jlbcwsJC1iWUTCED6OSw/FDoKYUMSbzwu7iiPsN1NYUMoJPD8kOhpxQyJPE7WjMzsxSlMtB64ff8aGxszLqEkilkAJ0clh8KPaWQIUkqA+327dvT2KxtgkITK2QAnRyWHwo9pZAhSSoDrRcVyI/lxZmLTCED6OSw/FDoKYUMSTxHa2ZmlqJUBlov/J4f1dXVWZdQMoUMoJPD8kOhpxQyJEllUQEv/G4myIsKmK1pyxcV8Bxtfpw5cybrEkqmkAF0clh+KPSUQoYkqQy0Xvg9PxRWUlLIADo5LD8UekohQxJfDGVmZpYiL/x+L0JzOLdv3y78A0QUMoBADs/R5k7hewqNDJDBHK2fdZwfo6OjWZdQMoUMoJPD8kOhpxQyJElloJ2fn09js7YJk5OTWZdQMoUMoJPD8kOhpxQyJPEcrZmZWYpSGWirqqrS2KxtQnt7e9YllEwhA+jksPxQ6CmFDEl8e484hflyhQygk8PyQ6GnFDIk8cVQ4hQuNFDIADo5LD8UekohQxLP0ZqZmaXIC7+L2717d9YllEwhA+jksPxQ6CmFDEk80IpraGjIuoSSKWQAnRyWHwo9pZAhSSoD7a1bt9LYrG3CxYsXsy6hZAoZQCeH5YdCTylkSOI5WjMzsxSlMtBWVHj8zova2tqsSyiZQgbQyWH5odBTChmSeOH3exF66LhZ2XhRAbM1bfmiAtPT02ls1jbh9OnTWZdQMoUMoJPD8kOhpxQyJPE5XnEKCzwoZACdHJYfCj2lkCGJB1ozM7MUeY72XoTmcBYWFgp/cZpCBhDI4Tna3Cl8T6GRATKYo52ZmUljs7YJw8PDWZdQMoUMoJPD8kOhpxQyJPHC7+KuX7+edQklU8gAOjksPxR6SiFDkuK/XzczM8uxxIE2hPD7IYSJEML59W7UC7/nR0dHR9YllEwhA+jksPxQ6CmFDEnW8472PwDv2chGFxYWNlWMlZ/CPc0KGUAnh+WHQk8pZEiSONDGGL8CTG5ko3Nzc5suyMprbGws6xJKppABdHJYfij0lEKGJJ6jNTMzS1HZFo4NIfQCvUt/ndnInG5O7QKu3XXvYPEs5ig2hQyglqPYx4ZCBtDoKYUMAHvW+od1PbAihNAKfCHGeGA9Xy2EcHKtG3eLQiEDaORQyADOkScKGUAjh0KGJD51bGZmlqL13N7zLPA3wFtDCGMhhI+mX5aZmZmGxDnaGOMHN7HdE5v4nLxRyAAaORQygHPkiUIG0MihkOG+UllUwMzMzBZ5jtbMzCxFZR1oN/O4xrwJIbwlhPDlEMJgCOFCCOHjWde0USGEnSGEl0MIZ5Yy/K9Z11SKEEJlCOF0COELWdeyWSGEkRDCuRDCQAihkGtIhhDqQwifCyFcWjo+vifrmjYqhPDWpX2w/GsqhPB01nVtVAjh55eO7fMhhGdDCDuzrmkzQggfX8pwoYj7Yb3Keuo4hPA48Drw/6z3VqC8CSG8CXhTjPFUCOFhoB/4r2OMFzMubd1CCAGojTG+HkLYDvw18PEY40sZl7YpIYRfAI4BdTHG92Vdz2aEEEaAYzHGwt4vGEL4A+A/xRh/L4SwA6iJMV7PuKxNCyFUAq8Ab48xXsm6nvUKIbyZxWO6M8Z4M4TwR8BfxBj/Q7aVbUwI4QDwWeBtwCzwHPAvYox/m2lhKSjrO9rNPK4xb2KM34wxnlr682vAIPDmbKvamLjo9aW/bl/6VcjJ+BBCM/DDwO9lXcuDLIRQBzwOfBogxjhb5EF2ybuA/69Ig+wq24DqEMI2oAYYz7iezdgHvBRjnI4x3gZeBN6fcU2p8BztfSw9qOMI8LWMS9mwpdOtA8AE8KUYY+EyLPkk8K+Aoq9UEYEvhhD6l56iVjRtwKvAv186jf97IYTarIsq0VPAs1kXsVExxleA3wRGgW8C/xBj/GK2VW3KeeDxEMJ3hRBqgPcCb8m4plR4oF1DCOEh4I+Bp2OMU1nXs1ExxvkYYxfQDLxt6TRNoYQQ3gdMxBj7s66lDN4RYzwK/BPgY0vTLEWyDTgK/N8xxiPADeAXsy1p85ZOff8I8B+zrmWjQgjfCfwo8I+AJqA2hPChbKvauBjjIPDrwJdYPG18BridaVEp8UB7D0vzmn8M9MUYP591PaVYOr33Ahtc6jAn3gH8yNL85meBd4YQPpNtSZsTYxxf+n0C+BMW56WKZAwYW3Vm5HMsDrxF9U+AUzHGb2VdyCb8IPB3McZXY4xzwOeB/yrjmjYlxvjpGOPRGOPjLE47ys3PggfauyxdSPRpYDDG+G+yrmczQgiPhBDql/5czeKBeSnTojYhxvhLMcbmGGMri6f5no8xFu4n9xBC7dKFdSydbn03i6fNCiPGeBX4RgjhrUsfehdQmAsE7+GDFPC08ZJR4LEQQs3S96t3sXgtSeGEEBqXfm8Bfozi7pP7KtvqPbDyuMYngF0hhDHgEzHGT5fza2yBdwA/CZxbmuME+J9ijH+RXUkb9ibgD5auqqwA/ijGWNhbYwQ8CvzJ4vdEtgH/b4zxuWxL2pSfA/qWTrsOA/9txvVsytJ84JPAP8u6ls2IMX4thPA54BSLp1pPU9ynK/1xCOG7gDngYzHGv8+6oDT4yVBmZmYp8qljMzOzFHmgNTMzS5EHWjMzsxR5oDUzM0uRB1ozM7MUeaA1MzNLkQdaMzOzFHmgNTMzS9H/D+KqE1IYaBxcAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 576x576 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "create_diagram(tree, 8., 8., min_val, max_val, 1)\n",
    "label_nodes(tree, 0)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 参考\n",
    "[1] Andrew Ng. Machine Learning[EB/OL]. StanfordUniversity,2014.https://www.coursera.org/course/ml\n",
    "\n",
    "[2] 李航. 统计学习方法[M]. 北京: 清华大学出版社,2019."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
